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。
Last updated
定义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。
Last updated