树状数组是对一个数组改变某个元素和求和比较实用的数据结构。

设a[1...N]为原数组,定义c[1...N]为对应的树状数组: 

c[i] = a[i - 2^k + 1] + a[i - 2^k + 2] + ... + a[i] 

其中k为i的二进制表示末尾0的个数,所以2^k即为i的二进制表示的最后一个1的权值. 

也就是说，把k表示成二进制1***10000，那么c[k]就是1***00001 + 1***00010 + ... + 1***10000这一段数的和。

所以2^k可以表示为n&(n^(n-1))或者更简单的n&(-n)，例如：

为了表示简便，假设现在一个int型为4位,最高位为符号位

int i=3&(-3);     此时i=1，3的二进制为0011,-3的二进制为1101(负数存的是补码）所以0011&1101=1

int Lowbit(int t) 

{ 

    return t & ( t ^ ( t - 1 ) ); 

}

求得：2^k=1000，

也就是说，把k表示成二进制1***10000，那么c[k]就是1***00001 + 1***00010 + ... + 1***10000这一段数的和。

设节点编号为x，由于c[i] = a[i - 2^k + 1] + a[i - 2^k + 2] + ... + a[i] 

那么这个节点管辖的区间为2^k个元素

修改一个节点，必须修改其所有祖先，最坏情况下为修改第一个元素，最多有log(n)的祖先。

如上图，对于c[8]，c[4]，假设c[4]的右兄弟节点为c[x]，那么c[4]和c[x]所管辖的节点数目是一样的，都是4个，即展开以后得到A数组中元素数目都是4，求c[4]节点父节点的编号，即是求父节点最大能扩展到多少，对于c[8]来说，可以认为他从左孩子的末端开始（即左孩子最大扩展的编号）计算，延伸的宽度即是左孩子的宽度，即为lowb(4)

修改一个节点，必须修改其所有祖先，最坏情况下为修改第一个元素，最多有log(n)的祖先。 

对a[n]进行修改后,需要相应的修改c数组中的p1, p2, p3...等一系列元素 

其中p1 = n,  pi+1 = pi + lowbit(pi)，

void Modify(int n, int delta)

{

while(n <= N)

{ 

c[n] += delta; 

n += lowbit(n);

}

}

当要查询a[1],a[2]...a[n]的元素之和时,需要累加c数组中的q1, q2, q3...等一系列元素 

其中q1  = n,qi+1 = qi - lowbit(qi) 

所以计算a[1] + a[2] + .. a[n]可以实现为:

int Sum(int n)

{

int result = 0;

while(n != 0)

{ 

result += c[n]; 

n -= lowbit(n); 

}

return result;

}

为什么是效率是log(n)的呢？以下给出证明： 

n = n – lowbit(n)这一步实际上等价于将n的二进制的最后一个1减去。而n的二进制里最多有log(n)个1，所以查询效率是log(n)的。

TreeArray