来源：
树状数组是一个查询和修改复杂度都为log(n)级别的区间统计的数据结构，在思想上类似于线段树。
相比线段树，树状数组需要的空间较少，编程复杂度也较低，但适用范围比线段树小。来观察一下这个图：
令这棵树的结点编号为C1，C2...Cn。令每个结点的值为这棵树的值的总和，那么容易发现：
C1 = A1 C2 = A1 + A2 C3 = A3 C4 = A1 + A2 + A3 + A4 C5 = A5 C6 = A5 + A6 C7 = A7 C8 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8 ... C16 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8 + A9 + A10 + A11 + A12 + A13 + A14 + A15 + A16 这里有一个有趣的性质，下午推了一下发现： 设节点编号为x，那么这个节点管辖的区间为2^k（其中k为x二进制末尾0的个数）个元素。因为这个区间最后一个元素必然为Ax， 所以很明显：Cn = A(n – 2^k + 1) + ... + An 算这个2^k有一个快捷的办法，定义一个函数如下即可：int lowbit(int x)
{
return x&(x^(x–1));
}
利用机器补码的特点，这个函数可以改得更方便
int lowbit(int i)
{
return i&(-i);
}
如果要把a[n]增加m，可以通过调用如下函数实现
void add(int i,int v)
{
while (i<=n)
{
a[i]+=v;
i+=lowbit(i);
}
}
如果要统计a[1]到a[n]之间的和，可以通过调用如下函数实现
int sum(int i)
{
int s=0;
while (i>0)
{
s+=a[i];
i-=lowbit(i);
}
return s;
}
java：
package tree_array;public class TreeArray { private int A[]; private int n; public TreeArray (int n) { A = new int[n+1]; this.n = n; } // 求2^k public int lowbit(int x) { return x & ( x ^ (x-1)); } // A[pos]增加m public void add(int pos, int m) { while(pos <= n) { A[pos] += m; pos += lowbit(pos); } } // 求前n项和 public int sum(int end) { int result = 0; while(end > 0) { result += A[end]; end -= lowbit(end); } return result; } public static void main(String[] args) { TreeArray treeArr = new TreeArray(10); for (int i = 1; i <= 10; i++) treeArr.add(i, i); System.out.println(treeArr.sum(10)); System.out.println(treeArr.sum(5)); }}
这是一维的情况，很容易能推广到二维。
POJ上用到树状数组的题目：