以前一直对树状数组这种结构并不感冒，因为觉得它能做到的事儿线段树也可以很好的完成。而且线段树应用更加灵活，可以说比树状数组的应用范围大很多。不过最近碰到两道题，都可以用树状数组这种结构很好的解决，代码非常精简单，特别是在二维应用的时候，用线段树非常麻烦，如果不是必要的话，不应当菜用线段树这种结构，而应用树状数组。稍微研究了下树状数组这种结构，写个总结吧。
树状数组它的每个元素并不像普通数组那样只保存自己的值，而是保存了从它开始前2^k个值的和(k为位置后面的二进制的0的个数）你可以看下图：
粉线色结点都只保持它自己的值，因为它们的二进制未尾0个数为0。绿色结点都保持了自己与它前一个值的和，蓝色结点保存了四个结点的值的和。棕色结点保存了8个结点的值的和。说了这么多，这种结构有什么用？它有什么优势呢？
它的主要优势就是可以快速求一段的和，即将求一段和的复杂度降到logN级别的，但是它增了修改一个元素的复杂度，使修改一个元素的复杂度也是logN级别的，不难知道，如果一个应用对于查询很多，每次查询都是一个区间的和，那么树状数组它的优势就很明显了。
问题一：怎么求一段元素的和？如果要求A[i –> j]，显然如果能快速求A[1->i-1]和A[1->j]那么问题就解决了。怎么快速转化呢？
因为每个位置它都包含了一段的值，如果这一段值被加进来后，可以快速跳到下一个值，再求。如求A[1->6]，那么知道6包括两个元素的和，下一次再求4，发现4包括四个元素的和，那么这两个和加进来就是结果。怎么快速求6的下一个元素呢？这就需要求出它二制后的0的个数的2的次幂，再与6作差即可。如6=(0000 0110)2，所以2^1=2 ,6-2=4, 4=(0000 0100), 所以2^2=4，4-4=0，结束。
int sum(int n) {
int ret = 0;
while(n > 0) {
ret += ss[n];
n -= lowbit(n);
}
return ret;
}
问题二：怎么快速求一个数二进制后面0的个数的2次幂？位运算。两种方法：x&(-x)或x&(x^(x-1))，它们都利用了位运算的特点，因为我们要求的就是从低位到到高位把遇到的第一个1保持不变，其余各位清0的一个操作！
inline int lowbit(int x) {
return x & (x ^ (x - 1));
}
问题三：怎么快速修改一个元素的值？从上面的图可以看到，修改一个元素的值，所有包含它的值的元素都会被修改。同样，它的变化只与求和有一些不同，求和是往下走，而修改值是往上走！
void change(int i, int value) {
while(i <= N) {
ss[i] += value;
i += lowbit(i);
}
}
变形应用：上面应用都是修改一个元素的值，求一段元素的和。那么它还可以进行什么样的操作呢？修改一段元素都增加或减少一个定值，查询一个元素的值！同样是logN级别的。问题是这样转化的：如果把a-b区间内的元素都要增加v，那么实际就可以把a元素增加v, b+1减少v，那么查询a元素的值呢？就是求sum(1->a)所有元素的和就行了！这样操作是否是正确的？正确性很容易证明，自己在纸上画画就会明白了。
二维树状数组与一维的情况类似。它也可以进行一段的操作，变形应用也可以。要注意的问题就是修改的值会变成四个角。
本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/MasterLuo/archive/2009/12/25/5073784.aspx