資料結構-----樹狀數組

樹狀數組是一種優雅的資料結構，利用的是字首和的思想，相當于是線段樹的一部分，常常用來快速解決區間求和問題，比相應的線段樹要快，因為常數小。

單點更新+區間求和

這個是樹狀數組最最基礎的應用了

給個例題  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