树状数组主要用于查询任意两位之间的所有元素之和，但是每次只能修改一个元素的值；经过简单修改可以在log(n)的复杂度下进行范围修改，但是这时只能查询其中一个元素的值。
一、和线段树比较：
1）树状数组能解决的线段树一般都能解决，线段树能解决的树状数组不一定能解决。
2）相比较而言，树状数组效率要高很多。
所以对于单点修改，单点查询来说最好的还是树状数组：
二、函数的基本作用：
1）update是用来修改树状数组的，如果是一般的算法只用修改改点就可，但是树状数组必须修改所有改点被管辖的区间。比如把a数组的 a[2]减去1，（令N=16）；则所有2被管辖的点有4，8，16都应该减去1，就是调用函数 update（2，-1）；
void update(int x,int num)
{
while(x<=N)
{
d[x]+=num;
x+=lowbit(x);
}
}
2）求和都是求1~x之间的和，所以区间求和是sum(r) - sum(l)。比如getSum（7）的话，就是求a[1]+a[2]+...a[7]。
int getSum(int x)
{
int s=0;
while(x>0)
{
s+=d[x];
x-=lowbit(x);
}
return s;
}
三、基础例题：
一维：
1 #include<stdio.h>
2 #include<string.h>
3 #include<math.h>
4 int a[50005];
5 int n;
6 int lowbit(int t)
7 {
8 return t&(-t);
9 }
10 void insert(int t,int d)
11 {
12 while(t<=n)
13 {
14 a[t]+=d;
15 t=t+lowbit(t);
16 }
17 }
18 long long getsum(int t)
19 {
20 long long sum=0;
21 while(t>0)
22 {
23 sum+=a[t];
24 t=t-lowbit(t);
25 }
26 return sum;
27 }
28 int main()
29 {
30 int T,i,j,k,t;
31 scanf("%d",&T);
32 t=0;
33 while(T--)
34 {
35 memset(a,0,sizeof(a));
36 scanf("%d",&n);
37 for(i=1;i<=n;i++)
38 {
39 scanf("%d",&k);
40 insert(i,k);
41 }
42 char str[10];
43 scanf("%s",str);
44 printf("Case %d:
",++t);
45 while(strcmp(str,"End")!=0)
46 {
47 int x,y;
48 scanf("%d%d",&x,&y);
49 if(strcmp(str,"Query")==0)
50 printf("%lld
",getsum(y)-getsum(x-1));
51 else if(strcmp(str,"Add")==0)
52 insert(x,y);
53 else if(strcmp(str,"Sub")==0)
54 insert(x,(-1)*y);
55 scanf("%s",str);
56 }
57 }
58 }
1 #include<stdio.h>
2 #include<iostream>
3 #include<string.h>
4 using namespace std;
5
6 const int MAXN=100010;
7 int c[MAXN];
8 int n;
9
10 int lowbit(int x)
11 {
12 return x&(-x);
13 }
14 void add(int i,int val)
15 {
16 while(i<=n)
17 {
18 c[i]+=val;
19 i+=lowbit(i);
20 }
21 }
22 int sum(int i)
23 {
24 int s=0;
25 while(i>0)
26 {
27 s+=c[i];
28 i-=lowbit(i);
29 }
30 return s;
31 }
32 int main()
33 {
34 int a,b;
35 while(scanf("%d",&n),n)
36 {
37 memset(c,0,sizeof(c));
38 for(int i=0;i<n;i++)
39 {
40 scanf("%d%d",&a,&b);
41 add(a,1);
42 add(b+1,-1);
43 }
44 for(int i=1;i<n;i++)
45 printf("%d ",sum(i));
46 printf("%d
",sum(n));
47 }
48 return 0;
49 }
POJ2352题意：某个星星的左下的星星数目代表它的等级，求0~n-1每个等级的星星数目分别有几个
1 #include<cstdio>
2 #include<iostream>
3 #include<cstring>
4 #include<algorithm>
5 using namespace std;
6 const int MAXN = 35010;
7 int c[MAXN];
8 int tot[MAXN];
9 int n;
10 int lowbit(int x)
11 {
12 return x&(-x);
13 }
14 int getsum(int i)
15 {
16 int s=0;
17 while(i>0)
18 {
19 s += c[i];
20 i -= lowbit(i);
21 }
22 return s;
23 }
24 void add(int li, int val)
25 {
26 while(li<=MAXN)
27 {
28 c[li] += val;
29 li += lowbit(li);
30 }
31 }
32 int main()
33 {
34 ///找前边有几个x，y都比当前小的
35 while(~scanf("%d",&n))
36 {
37 int x,y;
38 memset(c,0,sizeof(c));
39 memset(tot,0,sizeof(tot));
40 for(int j=1; j<=n; j++)
41 {
42 scanf("%d%d",&x,&y);
43 add(x+1,1);
44 tot[getsum(x+1)-1]++;///前边有getsum(x+1)-1个比当前小的数字
45 }
46 for(int j = 0; j < n ; j++)
47 printf("%d
",tot[j]);
48 }
49 return 0;
50 }
1 ///逆序对数是求前边有几个比当前更大的数字
2 ///POJ2352 是求前边有几个比当前更小的数字
3 ///按照从大到小排序后求前边有几个次序比他更小的就是逆序对数
4 #include<cstdio>
5 #include<iostream>
6 #include<cstring>
7 #include<algorithm>
8 #define ll long long
9 #define repu(i, a, b) for(int i = a; i < b; i ++)
10 using namespace std;
11 const int MAXN = 500010;
12 ll c[MAXN];
13 int n;
14 struct S
15 {
16 int val,pos;
17 bool operator < (const S& s) const
18 {
19 return val > s.val;
20 }
21 } a[MAXN];
22 int b[MAXN];
23 int lowbit(int x)
24 {
25 return x&(-x);
26 }
27 ll getsum(int i)
28 {
29 ll s = 0;
30 while(i>0)
31 {
32 s += c[i];
33 i -= lowbit(i);
34 }
35 return s;
36 }
37 void add(int li)
38 {
39 while(li<=MAXN)
40 {
41 c[li] += 1ll;
42 li += lowbit(li);
43 }
44 }
45 int main()
46 {
47 ///找前边有几个x，y都比当前小的
48 while(scanf("%d",&n),n)
49 {
50 int x,y,k;
51 ll sum = 0;
52 memset(c,0,sizeof(c));
53 repu(i,0,n)
54 {
55 scanf("%d",&a[i].val);
56 a[i].pos = i + 1;
57 }
58 sort(a,a+n);
59 repu(i,0,n)
60 {
61 x = a[i].pos;
62 add(x);
63 sum += getsum(x - 1);
64 }
65 printf("%I64d
",sum);
66 }
67 return 0;
68 }
二维：放了好久了已经，今天打BC突然一道博弈，用到二维区间求和，找线段树模板找不到，真的蒙圈了。
HDU5465：
题意：一个n*m的矩阵，然后两个操作：
1 l1,r1,l2,r2表示选取（l1,r1）到（l2,r2）子矩阵；
2 l r c 单点（l,r）的数改成c；
然后Alice和Bob轮流从选取的矩阵中找一个数字减掉d，直到选取的子矩阵中所有数字为0。问谁最终会赢。
分析：这是个博弈的题，而且当时在天津大学的板子上也找到了解决方法，就是两人从N堆石子中取石子，直到一方不能取。
因为是矩阵，累加时间复杂度太高，因此需要树状数组来减时间复杂度。
由于xor有前缀和性质，所以我们可以用一个二维bit来维护(1, 1)-(a, b)的矩阵的xor和，然后由sum(x2, y2) xor sum(x2, y1-1) xor sum(x1-1, y2) xor sum(x1-1, y1-1)sum(x2,y2) xor sum(x2,y1−1) xor sum(x1−1,y2) xor sum(x1−1,y1−1)来得到答案即可。单点修改在bit上是很容易的。
1 #include <cstdio>
2 #include <iostream>
3 #include <sstream>
4 #include <cmath>
5 #include <cstring>
6 #include <cstdlib>
7 #include <string>
8 #include <vector>
9 #include <map>
10 #include <set>
11 #include <queue>
12 #include <stack>
13 #include <algorithm>
14 #define ll long long
15 #define mem(m, a) memset(m, a, sizeof(m))
16 #define repu(i, a, b) for(int i = a; i < b; i++)
17 #define MAXN 100005
18 const double PI=-acos(-1.0);
19 using namespace std;
20 int num[510][510];
21 int p[510][510];
22 int lowbit(int x)
23 {
24 return x&(-x);
25 }
26 ///更新
27 int n,m;
28 void add(int x,int y,int val)
29 {
30 for(int i=x; i<=n; i+=lowbit(i))
31 {
32 for(int j=y; j<=m; j+=lowbit(j))
33 {
34 num[i][j] ^= val;
35 }
36 }
37 }
38 ///区间求和,不过是（1,1）到（x,y）
39 int query(int x,int y)
40 {
41 int ans=0;
42 for(int i=x; i>0; i-=lowbit(i))
43 {
44 for(int j=y; j>0; j-=lowbit(j))
45 {
46 ans ^= num[i][j];
47 }
48 }
49 return ans;
50 }
51 int main()
52 {
53 int op;
54 int a,b,c,d,q;
55 int T;
56 scanf("%d", &T);
57 while(T--)
58 {
59 mem(num,0);
60 scanf("%d%d%d",&n, &m, &q);
61 repu(i, 1, n + 1)
62 repu(j, 1, m + 1)
63 {
64 scanf("%d", &p[i][j]);
65 add(i,j,p[i][j]);
66 }
67 while(q--)
68 {
69 scanf("%d",&op);
70 if(op == 1)
71 {
72 scanf("%d%d%d%d",&a,&b,&c,&d);
73 int t = query(c,d)^query(a-1,b-1)^query(a-1,d)^query(c,b-1);
74 if(t==0) printf("No
");
75 else printf("Yes
");
76 }
77 else
78 {
79 scanf("%d%d%d",&a,&b,&c);
80 add(a,b,p[a][b]);
81 p[a][b] = c;
82 add(a,b,p[a][b]);
83 }
84 }
85 }
86 return 0;
87 }
注意区间求异或的时候：因为query只能求（1,1）~（x,y）之间的异或，所以有三部分是多余的，因此需要重新异或回来。
那三部分就是（a-1,b-1）,(c，b-1),（a-1,d）;不过原理我还是不明白