树状数组BinaryIndexedTree学习笔记

看了不少树状数组的资料，讲解大多十分清楚，但是都没有明确的推导过程，所以自己尝试不那么严谨地推导一下

一个长度为n的数组C，需要能修改任意位置的数，并求前k个数的和（或者连续k个数的和）

• 如果直接累加，则修改时间复杂度O(1)，求和时间复杂度O(n)


• 如果使用辅助数组存储前k个数的和，则修改时需要更新从当前位置到数组末尾的所有数，时间复杂度O(n)，求和时间复杂度O(1)

考虑平衡修改复杂度和求和复杂度，除非存储前k个数的和，否则求和复杂度不可能降为O(1)，所以考虑想办法降为O(log(n))

• 如果生成辅助数组D，将前k个数求和化作k的二进制形式每个1代表的数在辅助数组D中的值的和，则求和复杂度可以降为O(log(n))

考虑如何实现上述方案，即求辅助数组D

• 令数组C=(C₀,C₁,...,C_n-1)，辅助数组D=(D₀,D₁,...,D_n)，D₀=0


• 在k>0的情况下，设i=f(k)为k的二进制表示的从右数第一个1的位置（从0开始计算），则D[k]其实是包含从C[k-1]到C[k-2ⁱ]，共2ⁱ个数的和


• 由于k二进制表示从右数i右边的位置都是0，可知D[k]其实是对满足如下条件的所有C[j]求和：j二进制形式低i位从000...000、000...001、000...010一直遍历到111...111，第i位为0，高位同k相同


• 这样如果修改C[j]，同时需要依次修改满足以下条件的k：

1. 从右向左寻找j二进制形式中的0，找到则将0置为1，并将这位的右边全部置0，可以得到唯一的k，根据上面定义可知D[k]一定包含C[j]


2. 由于对于j二进制形式中为1的位置，设此位置为i‘，根据上面定义无法找到k，满足f(k)=i‘并且D[k]包含C[j]

• 综合1、2可知修改时间复杂度也为O(log(n))

上面假设的数组C下标从0~n-1，而辅助数组D的下标从0~n，由定义可知在k>0时D[k]一定包含C[k-1]，所以可以设E_i+1=C_i，得到新数组E=(E₁,E₂,...,E_n)代替数组C，此时数组E与辅助数组D一一对应

在数组修改（更新）的过程中，由于i+1等同于将i的最低0位置为1，并将此位右边全部置0，又由于最低的0位右边的位对于D[k]的查找没有影响，因此将数组C替换为数组E，修改E[j]的过程改为：先修改D[j]，然后从j二进制形式最低的非0位开始，从右向左寻找j二进制形式中的0，找到则将0置为1，并将这位的右边全部置0，得到k，修改D[k]

参考文献：

https://zh.wikipedia.org/wiki/%E6%A0%91%E7%8A%B6%E6%95%B0%E7%BB%84