Binary Indexed Tree（树状数组）是能够完成下述操作的数据结构（单点更新，区间求和）
给一个初始值全为0的数列a1,a2,....an
*给定i,计算a1+a2+....ai（前i项和）
*给定i和x,执行ai+=x
通常用树状数组来快速求任意一区间的和
如果我们想求从s到t的和，只要知道（从1到t的和）和（从1到s-1的和）这2个数相减，就是我们要求的区间和
，也就是说，使用树状数组，我们可以快速求某一区间所有数的和。
37
24
13
8
16
10
3
5
3
7
9
6
4
1
2
如果想要得到前i项的和，如果是前8项，直接输出37，如果是前7项和，我们只需要知道红色部分的值分别是24，10，1。就可以了。
这样我们可以发现，我们查询的时候，每个节点右儿子的值不需要了，因为这个节点的值减去其左儿子的值就是其
右儿子的值。所以我们可以这样建立树状数组。。。
8
4
0
2
0
6
0
1
0
3
0
5
0
7
0
上面是红色数字的是我们要建数组的编号（元素值为0的就是可以省略的左儿子的值。。。。）
首先我们把数组下标转化成二进制。。。。来看看有什么发现。。。
1 0001
2 0010
3 0011
4 0100
5 0101
6 0110
7 0111
8 1000
我们可以发现以1结尾的1，3，5，7数组的长度是1，最后有1个0的2，6数组的长度是2(包含2个元素)，而最后有2个0的4的长度是4(包含4个元素)。
这样在计算前i项和，需要从i开始，不断把当前位置i的值加入到结果中，并从i中减去i的二进制最低非0位对应的位，知道i变成0为止。
比如要计算前5项（二进制0101）的和，只需要知道bit[5和bit[4]（0100 是0101减去0001得到的）的值就可以了
int bit[MAX_N],n;//区间是[1,n] int sum(int i)//求前i项的和 { int s=0; while(i>0) { s+=bit[i]; i-=i&-i;//从i中减去i的二进制最低非0位对应的幂 } return s; } void add(int i,int x)//给ai加上x { while(i<=n) { bit[i]+=x; i+=i&-i; } }二维BIT就是在用一个一维BIT数组管理n个其他一维BIT数组，就是说一维BIT数组里存储的是单个值。。。。。
而二维BIT数组里存储的是一个一维BIT数组。。。。
int bit[MAX_N][MAX_N],n,m; int sum(int x,int y) { int res=0; int i,j; for(i=x;i>0;i-=i&-i) for(j=y;j>0;j-=j&-j) res+=bit[i][j]; return res; } int add(int x,int y,int v) { int i,j; for(i=x;i<=n;i+=i&-i) for(j=y;j<=m;j+=j&-j) bit[i][j]+=v; }此外还有 一维，二维的区间更新，单点查询。
int bit[MAX_N]; int sum(int x) { res=0; while(x>0) { res+=bit[x]; x-=x&-x; } } int add(int x,int v) { while(x<=n) { bit[x]+=v; x+=x&-x; } } int update(int x,int y,int v) { add(x,v); add(y+1,-v); }
int num[MAX_N]; int bit0[MAX_N]; int bit1[MAX_N]; int sum(int *a[],int x) { res=0; while(x>0) { res+=bit[x]; x-=x&-x; } } int add(int *a[],int x,int v) { while(x<=n) { bit[x]+=v; x+=x&-x; } } void init() { for(i=1;i<=n;i++) add(c0,i,num[i]-num[i-1]); add(c1,i,(i-1)*(num[i]-num[i-1])); } void update(int x,int y,int v) { add(c0,x,v);add(c0,y+1,v); add(c1,x,v*(x-1));add(c1,y+1,-y*v); } int query(int *a[],int *b[],int l,int r) { int sum0,sum1; sum0=(l-1)*sum(a,l-1)+sum(a,l-1); sum1=r*sum(b,r)+sum(b,r); return sum1-sum0; }
网上的大多数讲解不全面 ，特此给大家分享一个大神帖，把树状数组的所有变种都涵盖到了。。很全面
大神全面讲解树状数组
