树状数组专题

[update]树状数组第i位存的是[i - lowbit(i) + 1, i]的和。

树状数组上二分找第k个：

inline int getKth(int k) {    int ans = 0, t = pw[n];    while(t >= 0) {        if(((ans | (1 << t)) <= n) && ta[ans | (1 << t)] < k) {            k -= ta[ans | (1 << t)];            ans |= (1 << t);        }        t--;    }    return ans + 1;}

 

前言：

树状数组就算不理解也要强行背下来(很好背)，以后做题就会发现根本离不开它。

首先，什么是树状数组？

①是一种数据结构

②支持单点修改，区间求和。魔改后会支持区间加，单点求和，以及进化版的二维树状数组等等，在此按下不表。

③插入O(log₂n),查询O(log₂n)

原理是关于二进制的。我没怎么理解。

那么先放最基础的模板。

 

1 #define lowbit(x) (x&(-x)) 2 int tree[100010],n; 3 void add(int x,int v)///给x加上v,初始化 4 { 5     for(int i=x;i<=n;i+=lowbit(i)) tree[i]+=v; 6     return; 7 } 8 int getsum(int x)///查询x处的前缀和 9 {10     int ans=0;11     for(int i=x;i>0;i-=lowbit(i)) ans+=tree[i];12     return ans;13 }14 int ask(int l,int r)///查询区间和15 {16     if(l>r) return 0;17     return getsum(r)-getsum(l-1);18 }

 

十分之基础

 接下来就是一些例题与拓展应用。

P3368 模板树状数组2

这道题要区间加，单点差。考虑到这是个树状数组模板题(???????)，我们就考虑差分。

差分：b[i]=a[i]-a[i-1];

对于[l,r]+v,只需b[l]+v,b[r+1]-v即可

a[i]=∑(b[1]...b[i]);

那么我们就要对b[]实施单点改，区间求和。使用树状数组：

 

1 #include 
      
        2 #define lowbit(a) (a&(-a)) 3 using namespace std; 4 typedef long long LL; 5 const int N = 500010; 6 LL a[N],tree[N],n; 7 void add(int x,int v) 8 { 9     for(int i=x;i<=n;i+=lowbit(i)) tree[i]+=v;10     return;11 }12 LL getsum(int x)13 {14     LL ans=0;15     for(int i=x;i;i-=lowbit(i)) ans+=tree[i];16     return ans;17 }18 LL ask(int l,int r)19 {20     if(l>r) return 0;21     return getsum(r)-getsum(l-1);22 }23 int main()24 {25     int m,x,y,k,flag;26     scanf("%d%d",&n,&m);27     for(int i=1;i<=n;i++)28     {29         scanf("%d",&a[i]);30         add(i,a[i]-a[i-1]);31     }32     while(m--)33     {34         scanf("%d",&flag);35         if(flag==1)36         {37             scanf("%d%d%d",&x,&y,&k);38             add(x,k);39             add(y+1,-k);40         }41         else42         {43             scanf("%d",&x);44             printf("%lld\n",ask(1,x));45         }46     }47     return 0;48 }
      

 （当然也可以用线段树水过）

1 #include 
      
        2 using namespace std; 3 const int N = 500010; 4 typedef long long LL; 5 LL sum[4*N],tag[4*N]; 6 void down(int l,int r,int o) 7 { 8     if(tag[o]) 9     {10         tag[o<<1]+=tag[o];11         tag[o<<1|1]+=tag[o];12         int mid=(l+r)>>1;13         sum[o<<1]+=tag[o]*(mid-l+1);14         sum[o<<1|1]+=tag[o]*(r-mid);15         tag[o]=0;16     }17     return;18 }19 void update(int l,int r,int o)20 {21     sum[o]=sum[o<<1]+sum[o<<1|1];22     return;23 }24 void build(int l,int r,int o)25 {26     if(l==r)27     {28         scanf("%lld",&sum[o]);29         return;30     }31     int mid=(l+r)>>1;32     build(l,mid,o<<1);33     build(mid+1,r,o<<1|1);34     update(l,r,o);35     return;36 }37 void add(int L,int R,int v,int l,int r,int o)38 {39     if(L<=l&&r<=R)40     {41         sum[o]+=v;42         tag[o]+=v;///this!一开始我忘写了43         return;44     }45     int mid=(l+r)>>1;46     down(l,r,o);47     if(L<=mid) add(L,R,v,l,mid,o<<1);48     if(R>mid) add(L,R,v,mid+1,r,o<<1|1);49     update(l,r,o);50     return;51 }52 LL ask(int L,int R,int l,int r,int o)53 {54     if(L<=l&&r<=R) return sum[o];55     if(r
       
        
         >1;58     return ask(L,R,l,mid,o<<1)+ask(L,R,mid+1,r,o<<1|1);59 }60 int main()61 {62     int m,n,flag,x,y,k;63     scanf("%d%d",&n,&m);64     build(1,n,1);65     while(m--)66     {67         scanf("%d",&flag);68         if(flag==1)69         {70             scanf("%d%d%d",&x,&y,&k);71             add(x,y,k,1,n,1);72             //for(int i=1;i<=n;i++) printf("%d ",ask(i,i,1,n,1));73             //printf("\n");74         }75         else76         {77             scanf("%d",&x);78             printf("%lld\n",ask(x,x,1,n,1));79         }80     }81     return 0;82 }