HDU 1556 线段树或树状数组，插段求点-白红宇

HDU 1556 线段树或树状数组，插段求点

阅读量：4673 次

发布时间：2019-06-09

本文共 1453 字，大约阅读时间需要 4 分钟。

1、区间更新，单点查询

2、题意：n个气球，每次给(a,b)区间的气球涂一次色，问最后每个气球各涂了几次。

(1)树状数组

总结：树状数组是一个查询和修改复杂度都为log(n)的数据结构。主要用于查询任意两位之间的所有元素之和，但是每次只能修改一个元素的值。

这里改下思路可以用树状数组。在更新(a,b)时，向上更新，将a~n加1，b+1~n减1。查询点时，向下求和即可。

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #define F(i,a,b) for (int i=a;i
            
             0) { sum+=c[x]; x-=lowbit(x); } return sum;}int main(){ while(~scanf("%d",&n),n) { mes(c,0); int a,b; FF(i,1,n) { scanf("%d%d",&a,&b); update(a,1); update(b+1,-1); } F(i,1,n) printf("%d ",Sum(i)); printf("%d\n",Sum(n)); } return 0;}

View Code

(2)线段树+lazy思想

总结：lazy，更新时只到区间，可以节省很多时间。

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #define F(i,a,b) for (int i=a;i
            
             >1; build(o<<1,L,mid); build(o<<1|1,mid+1,R);}void update(int o,int l,int r,int L,int R){ if(l<=L&&R<=r) { c[o]++; return ; } //关键：只更新到区间，一开始更新到每个单独的点，果断T了，//然后用l==L&&R==r，又果断MLE int mid=(L+R)>>1; if(mid
             
              >1; query(o<<1,L,mid); query(o<<1|1,mid+1,R);}int main(){ while(~scanf("%d",&n) ,n ) { build(1,1,n); fill(ans+1,ans+1+n,0); //fil函数 int a,b; FF(i,1,n) { scanf("%d%d",&a,&b); update(1,a,b,1,n); } query(1,1,n); F(i,1,n) printf("%d ",ans[i]); printf("%d\n",ans[n]); } return 0;}