TOJ有道题，大意是有N个位置，每个位置有若干瓶子，Mike很淘气，他每次会增加或减少位置i的瓶子数，然后有M次询问，求位置A到B的瓶子数的和。最开始，我一直用最直观的做法，但是由于是O(n)的复杂度，所以一直超时。今天看了BIT的相关东西，才发现那个题其实是典型的BIT题目，而且是最基础的，但是就和RMQ问题一样，高效的算法背后深刻的数学理论还是不能很透彻的理解，这个只有靠以后熟练的慢慢来了：D
先来看一下树状数组的概念：树状数组是一种静态树状数据结构，它的首要作用是维护前缀和，即改变数组中某一元素a[i]的值，若要询问前N项的和，树状数组便可完美解决。时间复杂度O(logn)。
先来直观看一下树状数组的结构（图片来自http://fqq11679.blog.hexun.com/21722866_d.html#）
在上图中，红色的数组c[]便是树状数组。改变数组a的某一个元素i，则需要相应的改变数组c，若要询问前N项和，只需累加相应的c，而这当中一个核心的问题便是相应的数组c的下标问题。可以用位操作lowbit解决。c[i]=a[i-2^k+1]到a[i]的和，k是指i用二进制表示时末位0的个数，即将i表示成幂方和后最小的指数。利用位运算，我们可以得知2^k=i&(i^(i-1));
相应的代码为：
1 int lowbit(int n)
2 {
3 return n&(n^(n-1));
4 }
这样，当a[i]改变时，我们只需从c[i]开始一直向上回溯，改变路上相应的数组c的值，若要求前N项和，只需求N以前所有最大子树c[]的和。然后我们来看相应下标的操作：
修改a[i],则修改一路的父节点c[p], p=i-bit(i);
若要前i项求和，只需一路找子节点c[p], p=i-lowbit(i);
求前N项和：
1 int sum(int n)
2 {
3 int total=0;
4 while(n>0){
5 total+=c[n];
6 n-=lowbit(n);
7 }
8 return total;
9 }
TOJ 3505 Naughty mike
Code：
1 /*TOJ 3505 Naughty mike*/
2 #include<stdio.h> //注意在使用树状数组时下标一定不能从0开始
3 #include<string.h>
4 #define M 100002
5 int a[M],n;
6 int c[M];
7 int lowbit(int t) //关键的位操作确定数组下标
8 {
9 return t&(t^(t-1));
10 }
11 int sum(int end) //求前end项和的函数，通过不断累加最大子树得到
12 {
13 int i;
14 int total=0;
15 while(end>0){
16 total+=c[end];
17 end-=lowbit(end);
18 }
19 return total;
20 }
21 void modify(int t,int key) //对数组某一项进行修改时，只需沿该项一直向上回溯修改相应的数组c
22 {
23 while(t<=n){
24 c[t]+=key;
25 t+=lowbit(t);
26 }
27 }
28 int main()
29 {
30 int i,j,k,m,cas;
31 char e[50];
32 scanf("%d",&cas);
33 while(cas--){
34 scanf("%d",&n);
35 memset(c,0,sizeof(c));
36 for(i=1;i<=n;i++){
37 scanf("%d",&a[i]);
38 modify(i,a[i]);
39 }
40 scanf("%d",&m);
41 while(m--){
42 scanf("%s%d%d",e,&i,&j);
43 if(e[0]=='A'){
44 modify(i,j);
45 a[i]+=j;
46 }
47 else if(e[0]=='D'){
48 if(j>=a[i]) j=(-1)*a[i]; //由于可能删除的比现有的还多，需要分开考虑
49 else j*=(-1);
50 modify(i,j);
51 a[i]+=j;
52 }
53 else
54 printf("%d\n",sum(j)-sum(i-1)); //区间[i,j]的和
55 }
56 }
57 }
58