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

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

单点更新+区间求和

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

给个例题  hdu 1166

1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <set>
 5 #include <algorithm>
 6 #include <map>
 7 #include <queue>
 8 #include<cmath>
 9 #include<vector>
10 #define maxn 50010
11 #define maxm 100010
12 #define mod 1000000000000000000
13 #define INF 0x3f3f3f3f
14 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){//建立bit
22         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的前缀和是不断变化的，可以用两个树状数组来维护。

poj3468

1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <set>
 5 #include <algorithm>
 6 #include <map>
 7 #include <queue>
 8 #include<cmath>
 9 #include<vector>
10 #define maxn 100010
11 #define maxm 100010
12 #define mod 1000000000000000000
13 #define INF 0x3f3f3f3f
14 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){//建立bit
23         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 }      

View Code

树状数组对于线段树来说写起来简单且效率高，但很多的问题是树状数组无法解决的。

转载于:https://www.cnblogs.com/shuzy/p/3815109.html