树状数组

给定一个区间，如果要频繁修改该区间内的元素，且频繁查询该区间内任意小区间的元素之和时，可以用树状数组。

普通的一次修改时间复杂度是O(1)，而查询的时间复杂度是O(n). 树状数组的修改和查询的时间复杂度均为O(logn)

给定区间1-->n，区间内对应的元素为a[i] (1 <= i <= n )

树状数组是这样一个数组c

c[i] = a[i - 2^k + 1] + ... + a[i] , k 为i在二进制下末尾0的个数（所以树状数组不能从0开始，只能从1开始)，也即2^k是i在二进制下，第一个不为0的bit所表示的大小

1 int lowbit(int t)
2 {
3     return t&(-t);
4 }

lowbit(t); 的作用是求出t在二进制下，第一个不为0的bit所表示的大小
4(10) = 0000 0100(2) lowbit(4) = 4;
-4(10) = 1111 1100(2) 4&(-4) = 0000 0100
5(10) = 0000 0101(2) lowbit(5) = 1
-5(10) = 1111 1011(2) 5&(-5) = 0000 0001

如果，当要修改一个元素a[pos]时，就要修改c[pos]及其c[pos]的父亲，c[pos]父亲的父亲，即c[pos]往根结点一路上溯，不断修改c[]即可

c[pos]的父结点的下标为 pos += lowbit(pos)

1 void modify(int pos, int val)//当a[pos]发生改变时
2 {
3     while(pos <= n)
4     {
5         c[pos] += val;//c[pos] 肯定包含a[pos] ,但是之后的c数组，哪个又包含a[pos]呢
6         pos += lowbit(pos);//c[pos]的父结点的下标为 pos += lowbit(pos)
7     }
8 }

如图，如果求前n项的和，比如n=6时，c[6] = a[5] + a[6],c[6]包含lowbit(6)项，即2项，所以还要求得前4项的和，即n-=lowbit(n)

 1 int getSum(int pos)
 2 {
 3     int sum = 0;
 4     while(pos >= 1)
 5     {
 6         sum += c[pos];
 7         pos -= lowbit(pos);
 8     }
 9     return sum;
10 }

hdu1166敌兵布阵 http://acm.hdu.edu.cn/showproblem.php?pid=1166

 1 #include <stdio.h>
 2 #include <string.h>
 3 const int N = 50000 + 10;
 4 int c[N], n;
 5 int lowbit(int t)
 6 {
 7     return t&(-t);
 8 }
 9 void modify(int pos, int val)//当a[pos]发生改变时
10 {
11     while(pos <= n)
12     {
13         c[pos] += val;//c[pos] 肯定包含a[pos] ,但是之后的c数组，哪个又包含a[pos]呢
14         pos += lowbit(pos);//c[pos]的父结点的下标为 pos += lowbit(pos)
15     }
16 }
17 int getSum(int pos)
18 {
19     int sum = 0;
20     while(pos >= 1)
21     {
22         sum += c[pos];
23         pos -= lowbit(pos);
24     }
25     return sum;
26 }
27 int main()
28 {
29     int t, val, a, b, i, tCase = 1;
30     char op[10];
31     scanf("%d",&t);
32     while(t--)
33     {
34         memset(c, 0, sizeof(c));
35         scanf("%d",&n);
36         for(i=1; i<=n; ++i)
37         {
38             scanf("%d",&val);
39             modify(i, val);
40         }
41         printf("Case %d:
",tCase++);
42         while(true)
43         {
44             scanf("%s",op);
45             if(op[0] == 'E')
46                 break;
47             if(op[0] == 'Q')
48             {
49                 scanf("%d%d",&a,&b);
50                 int ans = getSum(b);
51                 if(a - 1 >= 1)
52                     ans -= getSum(a-1);
53                 printf("%d
",ans);
54             }
55             else if(op[0] == 'A')
56             {
57                 scanf("%d%d",&a,&b);
58                 modify(a, b);
59             }
60             else
61             {
62                 scanf("%d%d",&a,&b);
63                 modify(a, -b);
64             }
65         }
66 
67     }
68     return 0;
69 }

View Code

蓝桥杯小朋友排队 http://lx.lanqiao.org/problem.page?gpid=T123

只要算出每个小朋友要移动的次数，那么就能算出不开心的程度。从而算出总的不开心程度。

每个小朋友要移动的次数等于，左边大于它的数字的个数和右边小于它的数字的个数。即逆序数，

如果用暴力，时间复杂度是O(N*N)。逆序数可以用树状数组求，时间复杂度是O(N*logN）

 1 #include <stdio.h>
 2 #include <string.h>
 3 typedef __int64 LL;
 4 const int N = 100000 + 10;    
 5 const int M = 1000000 + 10;
 6 LL c[M+1],n,unHappy[N],a[N],b[N];
 7 void init()    
 8 {
 9     for(int i=1; i<N; ++i)
10         unHappy[i] = unHappy[i-1] + i;
11 }
12 int lowbit(int x)
13 {
14     return x&-x;
15 }
16 void modify(int pos, int val)
17 {
18     while(pos<=M)
19     {
20         c[pos] += val;
21         pos += lowbit(pos);
22     }
23 
24 }
25 int sum(int pos)
26 {
27     int ret = 0;
28     while(pos)
29     {
30         ret += c[pos];
31         pos -= lowbit(pos);
32     }
33     return ret;
34 }
35 int main()
36 {
37     init();
38     scanf("%d",&n);
39     LL i,x,ans = 0;
40     for(i=1; i<=n; ++i)
41     {
42         scanf("%I64d",&a[i]);
43         a[i]++;
44         b[i] += sum(M) - sum(a[i]);
45         modify(a[i],1);
46     }
47     memset(c,0,sizeof(c));
48     for(i=n; i>=1; --i)
49     {
50         b[i] += sum(a[i]-1);
51         modify(a[i],1);
52         ans += unHappy[b[i]];
53     }
54     printf("%I64d
",ans);
55     return 0;
56 }

View Code

扩展---二维树状数组

一维树状数组很容易扩展到二维，二维树状数组如下所示：

C[x][y] = sum(A[i][j])

其中，x-lowbit[x]+1 <= i<=x且y-lowbit[y]+1 <= j <=y

http://acm.fafu.edu.cn/problem.php?id=1100

一个由数字构成的大矩阵，能进行两种操作

1) 对矩阵里的某个数加上一个整数（可正可负）

2) 查询某个子矩阵里所有数字的和

要求对每次查询，输出结果

要求矩形（L,B)左上角的坐标，(R,T)右下角的坐标

树状数组的getSum(R,t)函数是获得(1,1)到(R,T)的所有元素和，所以要减去getSum(L,B-1), 减去getSum(L-1,T) ，然后加上getSum(L-1,B-1)

树状数组解法：

 1 #include <stdio.h>
 2 #include <string.h>
 3 const int N = 1024 + 10;
 4 int c[N][N], n;
 5 void init()
 6 {
 7     for(int i=0; i<=n; ++i)
 8         for(int j=0; j<=n; ++j)
 9             c[i][j] = 0;
10 }
11 int lowbit(int t)
12 {
13     return t & (-t);
14 }
15 void modify(int x, int y, int val)
16 {
17     for(int i=x; i<=n; i+=lowbit(i))
18         for(int j=y; j<=n; j+=lowbit(j))
19             c[i][j] += val;
20 }
21 int getSum(int x, int y)
22 {
23     int ans = 0;
24     for(int i=x; i>=1; i-=lowbit(i))
25         for(int j=y; j>=1; j-=lowbit(j))
26             ans += c[i][j];
27     return ans;
28 }
29 int main()
30 {
31     int op,x, y, a, l, b, r, t;
32     while(scanf("%d%d",&x,&n)!=EOF)
33     {
34         init();
35         while(scanf("%d",&op) && op != 3)
36         {
37             switch(op)
38             {
39             case 1:
40                 scanf("%d%d%d",&x,&y,&a);
41                 ++x; ++y;
42                 modify(x, y, a);
43                 break;
44             case 2:
45                 scanf("%d%d%d%d",&l,&b,&r,&t);
46                 ++l; ++b; ++r; ++t;
47                 printf("%d
",getSum(r,t) + getSum(l-1,b-1) - getSum( r,b-1 )-getSum(l-1,t) ); 
48                 break;
49             }
50         }
51     }
52     return 0;
53 }

View Code

线段树解法:

  1 /*
  2 0 4
  3 1 1 2 3
  4 2 0 0 2 2
  5 1 1 1 2
  6 1 1 2 -1
  7 2 1 1 2 3
  8 3
  9 多重二分--->线段树的每个结点也是一颗树
 10 将x二分，每次将x二分的情况下再将y二分
 11 */
 12 //#define _CRT_SECURE_NO_DEPRECATE
 13 #include <iostream>
 14 #include <string.h>
 15 #include <stdio.h>
 16 using namespace std;
 17 typedef __int64 LL;
 18 const int N = 1024 + 10;
 19 int sum[N * 3][N * 3];
 20 int n,op, x, y, v, L,B,R,T;
 21 LL ans;
 22 void sub_update(int f, int sLoc, int val, int l, int r, int rt)
 23 {
 24     if(l == r)
 25     {
 26         sum[f][rt] += val;
 27         return;
 28     }
 29     int mid = (l + r) >> 1;
 30     if(sLoc <= mid)
 31         sub_update(f, sLoc, val, l, mid, rt<<1);
 32     else
 33         sub_update(f, sLoc, val, mid+1, r, rt<<1|1);
 34     sum[f][rt] = sum[f][rt<<1] + sum[f][rt<<1|1];
 35 }
 36 void update(int fLoc, int sLoc, int val, int l, int r, int rt)
 37 {
 38     sub_update(rt, sLoc, val, 1, n, 1);
 39     if(l == r)
 40         return;
 41     int mid = (l + r) >> 1;
 42     if(fLoc <= mid)
 43         update(fLoc, sLoc, val, l ,mid, rt<<1);
 44     else
 45         update(fLoc, sLoc, val, mid+1, r, rt<<1|1);
 46 }
 47 
 48 LL sub_query(int f, int sL, int sR, int l, int r, int rt)
 49 {
 50     if(sL == l && sR == r)
 51         return sum[f][rt];
 52     int mid = (l + r) >> 1;
 53     LL ret = 0;
 54     if(sR <= mid)
 55         ret += sub_query(f, sL, sR, l, mid, rt<<1);
 56     else if(sL > mid)
 57         ret += sub_query(f, sL, sR, mid+1, r, rt<<1|1);
 58     else
 59     {
 60         ret += sub_query(f, sL, mid, l, mid, rt<<1);
 61         ret += sub_query(f, mid+1, sR, mid+1, r, rt<<1|1);
 62     }
 63     return ret;
 64 }
 65 LL query(int fL, int fR, int sL, int sR, int l, int r, int rt)
 66 {
 67     if(fL == l && fR == r)
 68         return sub_query(rt, sL, sR, 1, n, 1);
 69     int mid = (l + r) >> 1;
 70     LL ret = 0;
 71     if(fR <= mid)
 72         ret += query(fL, fR, sL, sR, l, mid, rt<<1);
 73     else if(fL > mid)
 74         ret += query(fL, fR, sL, sR, mid+1, r, rt<<1|1);
 75     else
 76     {
 77         ret += query(fL, mid, sL, sR, l, mid, rt<<1);
 78         ret += query(mid+1, fR, sL, sR, mid+1, r, rt<<1|1);
 79     }
 80     return ret;
 81 }
 82 void input(int &x)
 83 {
 84     char ch = getchar();
 85     bool flag = ch == '-';
 86     while(ch<'0' || ch>'9')
 87     {
 88         ch = getchar();
 89         if(ch == '-')
 90             flag = true;
 91     }
 92     x = 0;
 93     while(ch>='0' && ch<='9')
 94     {
 95         x = x * 10 + ch -'0';
 96         ch = getchar();
 97     }
 98     x = flag ? -x : x;
 99 }
100 int main()
101 {
102     while(scanf("%d%d",&op,&n)!=EOF)
103     {
104         ++n;
105         memset(sum, 0, sizeof(sum));
106         while(true)
107         {
108             //scanf("%d",&op);
109             input(op);
110             if(op == 1)
111             {
112                 //scanf("%d%d%d",&x,&y,&v);
113                 input(x);input(y);input(v);
114                 ++x; ++y;
115                 update(x, y, v, 1, n, 1);
116             }
117             else if(op == 2)
118             {
119                 input(L);input(B);input(R);input(T);
120                 //scanf("%d%d%d%d",&L,&B,&R,&T);
121                 ++L; ++B; ++R; ++T;
122                 printf("%I64d
",query(L, R, B, T, 1, n, 1));
123             }
124             else
125                 break;
126         }
127     }
128 }

View Code

二维线段树入门：http://wenku.baidu.com/view/bdc5eb0216fc700aba68fc05.html