吃透 Binary Indexed Trees （树状数组）

简介

Binary Indexed Trees（中文名为树状数组，下文简称为BIT）是一种特殊的数据结构，适用于高效计算数列的前缀和， 区间和。

时间复杂度：

1. 任意前缀和、区间和：O(logn)
2. 单点值修改：O(logn)

空间复杂度： O(n) 。

虽然 BIT 名称中带有 tree 这个词，但是实际存储时是利用数组进行存储，记nums为原始数组和 BIT为 BIT 数组，我们观察的是nums，但实际操作的是BIT。
下图就是初始化后的BIT情况，横轴为数组的下标i，纵轴为下标数值对应的lowestbit，长方形表示BIT[i]涵盖的元素的范围。

image
可以看到每个数组下标的lowestbit（也就是图中描黑的部分）在形态上构成了一棵树的形状，这也是名称中 tree 的来源。并且对于每个下标表示成的tree node有以下特性。

(1)假如i是左子节点，那么其父节点下标为i + lowestbit(i)，节点 4 为左子节点，父节点为节点 8（ 4 + lowestbit(4) = 4 + (100) = 4 + 4 = 8）
(2)假如i是右子节点，那么其父节点下标为i - lowestbit(i)，节点 12 为左子节点，父节点为节点 8 （ 12 - lowestbit(12) = 12 - (100) =12 - 4 = 8）

上面这两个特性非常重要，也是我们进行后文分析的重要基础。

更新数值

由图可知，BIT 中某些节点是包含其他节点的值得，所以在更新节点时，要同时更新这些包含节点的节点，例如更新节点 6 时，由于节点 8 和节点 16 包含节点 6 的值，所以也需要更新，那么如何判断更新节点 6 时，需要同时更新的节点是 8 和 16 呢？
若是按照树结构来找：

1. 先找节点 6 的父节点 6 - lowestbit(6) = 4
2. 找节点 4 的父节点 4 + lowestbit(4) = 8
3. 找节点 8 的父节点 8 + lowestbit(8) = 16
4. 共找到节点 4 8 16 三个节点
5. 其中节点 6 在节点 4 的右子树中，所以节点 4 是不包含节点 6 的
6. 节点 6 在节点 8 16 的左子树中，包含节点 6
7. 所以更新节点 8 16

这是顺序逻辑，那有没有办法直接越过节点 4 ，而去寻找节点 8 16 呢？

观察图就可以发现，对于节点 6 而言，它与父节点 4 的距离，跟与祖节点 8 的距离是一样的，都是lowestbit(6) = 2。
那么我们就可以用6 + lowestbit(6) = 8的方式来越过节点 4 直接寻找到节点 8。
而6 + lowestbit(6)与左子节点寻找父节点公式i + lowestbit(i)相同，所以寻找含有节点 6 的节点 8 16，我们可以只用i + lowestbit(i)来完成：

while(i < BIT.length)
{
    BIT[i] += offset
    i = i + lowestbit(i)
}

区间求和

如若求 nums 前 n 个元素的和，观察图可知，将此节点以及不断获取其作为右节点时的父节点，然后加和就可以了。

var sum = 0
while(i > 0)
{
    sum += BIT[i]
    i = i - lowestbit(i)
}

例如求 nums[0, 7] 的和，则通过上述代码和分别获得 BIT[7]、 BIT[6]、 BIT[4]，sum = BIT[7] + BIT[6] + BIT[4]，即为结果。
若是求区间和的话，例如 nums[5, 10]，则是 nums[0, 10] - nums[0, 5] 即可。

参考：Binary Indexed Trees 简介（重点帮助我理解了树状数组的结构，以及 i - lowestbit(i)、i + lowestbit(i) 与节点的关系，里面的BIT[i]公式感觉并不正确）