1、简述
树状数组(binary indexed tree)，是一种设计方案新奇的二维数组构造，它可以高效率地获得二维数组中持续n数量的和。归纳说，树状数组一般 用以处理下列难题：二维数组{a}中的原素很有可能持续的被改动，怎么才能迅速地获得持续好多个数的和？
2、树状数组操作过程
传统式二维数组(共n个原素)的原素改动和持续原素求饶的复杂性各自为O(1)和O(n)。树状数组根据将线性结构转化成伪树形结构构造（线性结构只有逐一扫描仪原素，而树形结构构造能够完成跳跃性扫描仪），促使改动和求饶复杂性均为O(lgn)，进一步提高了总体高效率。
给出编码序列（数列）A，大家设一个二维数组C考虑
C[i] = A[i–2^k 1] … A[i]
在其中，k为i在二进制下结尾0的数量，i从1逐渐算！
则大家称C为树状数组。
下边的难题是，给出i，怎样求2^k?
回答非常简单：2^k=i&(i^(i-1)) ，也就是i&(-i)
下边开展表述：
以i=6为例子（留意：a_x表明数据a是x进制表明方式）： (i)_10 = (0110)_2 (i-1)_10=(0101)_2 i xor (i-1) =(0011)_2 i and (i xor (i-1)) =(0010)_2 2^k = 2 C[6] = C[6-2 1] … A[6]=A[5] A[6]
二维数组C的实际含意如下图所显示：
在我们改动A[i]的值时，能够从C[i]往根节点一路追溯到，调节这条道路上的全部C[]就可以，这一实际操作的复杂性在最坏状况下便是树的高宽比即O(logn)。此外，针对求数列的前n项和，只需寻找n之前的全部较大 子树，把其根节点的C加起來就可以。不会太难发觉，这种子树的数量是n在二进制时1的数量，换句话说是把n进行成2的幂方和时的项数,因而，求饶实际操作的复杂性也是O(logn)。
树状数组能迅速求随意区段的和：A[i] A[i 1] … A[j]，设sum(k) = A[1] A[2] … A[k]，则A[i] A[i 1] … A[j] = sum(j)-sum(i-1)。
下边得出树状数组的C语言完成：
//求2^k
int lowbit(int t)
{
return t & ( t ^ ( t - 1 ) );
}
//求前n项和
int sum(int end)
{
int sum = 0;
while(end > 0)
{
sum = in[end];
end -= lowbit(end);
}
return sum;
}
//提升某一原素的尺寸
void plus(int pos, int num)
{
while(pos <= n)
{
in[pos] = num;
pos = lowbit(pos);
}
}
3、拓展——二维树状数组
一维树状数组非常容易拓展到二维，二维树状数组以下所显示：
C[x][y] = sum(A[i][j])
在其中，x-lowbit[x] 1 <= i<=x且y-lowbit[y] 1 <= j <=y
4、运用
（1） 一维树状数组：
参照：http://hi.baidu.com/lilu03555/blog/item/4118f04429739580b3b7dc74.html
（2） 二维树状数组：
一个由数据组成的大引流矩阵，能开展二种实际操作
1) 对引流矩阵里的某一数再加上一个整数金额（可正可负）
2) 查看某一子引流矩阵里全部数据的和
规定对每一次查看，輸出結果
5、小结
树状数组最开始是在设计方案压缩算法时发觉的（见参考文献1），如今也会常常术语维护保养子序列和。它与线段树（实际见：算法设计之线段树）较为在思想方面相近，比线段树节约室内空间且程序编写复杂性低，但应用范畴比线段树小（如查看每一个区段极小值难题）。
6、参考文献
（1） Binary Indexed Trees：
http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees
（2） 吴豪文章内容《树状数组》：
http://www.java3z.com/cwbwebhome/article/article19/zip/treearray.zip
（3） 郭炜文章内容《线段树和树状数组》：
http://poj.org/summerschool/1_interval_tree.pdf
