数据结构-----树状数组-白红宇

数据结构-----树状数组

阅读量：6914 次

发布时间：2019-06-27

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

树状数组是一种优雅的数据结构，利用的是前缀和的思想，相当于是线段树的一部分，常常用来快速解决区间求和问题，比相应的线段树要快，因为常数小。

单点更新+区间求和

这个是树状数组最最基础的应用了

给个例题

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
            7 #include 
            
              8 #include
             
               9 #include
              
               10 #define maxn 5001011 #define maxm 10001012 #define mod 100000000000000000013 #define INF 0x3f3f3f3f14 using namespace std;15 inline int lowbit(int x){16 return x&-x;17 }18 struct BIT{19 int N;20 int bit[maxn*2];21 void init(int *a,int n){ //建立bit22 N=n;23 memset(bit,0,sizeof(bit));24 for(int i=1;i<=N;++i){25 add(i,a[i]);26 }27 }28 int sum(int x){ //[1,x]前缀和29 int ans =0;30 for(int i=x;i>0;i-=lowbit(i))ans+=bit[i];31 return ans;32 }33 void add(int x,int v){ //单点修改34 for(int i=x;i<=N;i+=lowbit(i))bit[i]+=v;35 }36 }T;37 int a[maxn];//原数组38 int main (){39 int t;40 int n;41 scanf("%d",&t);42 for(int Case=1;Case<=t;++Case){43 scanf("%d",&n);44 for(int i=1;i<=n;++i)scanf("%d",&a[i]);45 T.init(a,n);46 char cmd[10];47 printf("Case %d:\n",Case);48 while(scanf("%s",&cmd)){49 if(strcmp(cmd,"End")==0)break;50 int x,y;51 scanf("%d%d",&x,&y);52 if(strcmp(cmd,"Query")==0)printf("%d\n",T.sum(y)-T.sum(x-1));53 else if(strcmp(cmd,"Add")==0)T.add(x,y);54 else T.add(x,-y);55 }56 }57 }

View Code

区间更新+区间求和

首先，看更新操作update(s, t, d)把区间A[s]…A[t]都增加d，我们引入一个数组delta[i]，表示

A[i]…A[n]的共同增量，n是数组的大小。那么update操作可以转化为：

1）令delta[s] = delta[s] + d，表示将A[s]…A[n]同时增加d，但这样A[t+1]…A[n]就多加了d，所以

2）再令delta[t+1] = delta[t+1] – d，表示将A[t+1]…A[n]同时减d

然后来看查询操作query(s, t)，求A[s]…A[t]的区间和，转化为求前缀和，设sum[i] = A[1]+…+A[i]，则

A[s]+…+A[t] = sum[t] – sum[s-1]，

那么前缀和sum[x]又如何求呢？它由两部分组成，一是数组的原始和，二是该区间内的累计增量和, 把数组A的原始

值保存在数组org中，并且delta[i]对sum[x]的贡献值为delta[i]*(x+1-i)，那么

sum[x] = org[1]+…+org[x] + delta[1]*x + delta[2]*(x-1) + delta[3]*(x-2)+…+delta[x]*1

= org[1]+…+org[x] + segma(delta[i]*(x+1-i))

= segma(org[i]) + (x+1)*segma(delta[i]) – segma(delta[i]*i)，1 <= i <= x

这其实就是三个数组org[i], delta[i]和delta[i]*i的前缀和，org[i]的前缀和保持不变，事先就可以求出来，delta[i]和

delta[i]*i的前缀和是不断变化的，可以用两个树状数组来维护。

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
            7 #include 
            
              8 #include
             
               9 #include
              
               10 #define maxn 10001011 #define maxm 10001012 #define mod 100000000000000000013 #define INF 0x3f3f3f3f14 using namespace std;15 typedef long long ll;16 inline int lowbit(int x){17 return x&-x;18 }19 struct BIT{20 int n;21 ll bit[maxn*2],bit2[maxn*2];22 void init(int N){ //建立bit23 n=N;24 memset(bit,0,sizeof(bit));25 memset(bit2,0,sizeof(bit2));26 }27 void add(ll *t,int x,ll v){ //单点加减28 for(int i=x;i<=n;i+=lowbit(i))t[i]+=v;29 }30 ll sum(ll *t,int x){ //[1,x]前缀和31 ll ans=0;32 for(int i=x;i>0;i-=lowbit(i))ans+=t[i];33 return ans;34 }35 void update(int l,int r,ll k){ //区间加减36 add(bit,l,k);37 add(bit,r+1,-k);38 add(bit2,l,k*l);39 add(bit2,r+1,-k*(r+1));40 }41 ll getsum(int x){42 return sum(bit,x)*(x+1)-sum(bit2,x);43 }44 ll query(int l,int r){ //区间求和45 return getsum(r)-getsum(l-1);46 }47 }T;48 ll a[maxn];49 int main (){50 int n,m;51 while(scanf("%d%d",&n,&m)!=EOF){52 T.init(n);53 for(int i=1;i<=n;++i){54 scanf("%lld",&a[i]);55 T.update(i,i,a[i]);56 }57 char cmd[10];58 while(m--){59 scanf("%s",&cmd);60 if(cmd[0]=='Q'){61 int x,y;62 scanf("%d%d",&x,&y);63 printf("%lld\n",T.query(x,y));64 }65 else {66 int x,y;67 ll z;68 scanf("%d%d%lld",&x,&y,&z);69 T.update(x,y,z);70 }71 }72 }73 }