Comment on page
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];
Last modified 3yr ago