Binary Indexed Tree

定义C[i]的值为它的所有叶子结点的权值的总和.

C[i]的表达式:

C[i]=A[i]+A[i-1]+....+A[i-2^k+1]

k代表i的二进制的最后连续0的个数。

C[i]还有一种更加普适的定义，它表示的其实是一段原数组A的连续区间和。区间的左端点为i - 2^k + 1，右端点为i。

将C[]数组的结点序号转化为二进制。
1=(001) C[1]=A[1];
2=(010) C[2]=A[1]+A[2];
3=(011) C[3]=A[3];
4=(100) C[4]=A[1]+A[2]+A[3]+A[4];
5=(101) C[5]=A[5];
6=(110) C[6]=A[5]+A[6];
7=(111) C[7]=A[7];
8=(1000) C[8]=A[1]+A[2]+A[3]+A[4]+A[5]+A[6]+A[7]+A[8];