简介
Binary Indexed Trees（中文名为树状数组，下文简称为BIT）是一种特殊的数据结构，适用于高效计算数列的前缀和， 区间和。
时间复杂度：
- 任意前缀和、区间和：O(logn)
- 单点值修改：O(logn)
空间复杂度： O(n) 。
虽然 BIT 名称中带有 tree 这个词，但是实际存储时是利用数组进行存储，记nums为原始数组和 BIT为 BIT 数组，我们观察的是nums，但实际操作的是BIT。
下图就是初始化后的BIT情况，横轴为数组的下标i，纵轴为下标数值对应的lowestbit，长方形表示BIT[i]涵盖的元素的范围。
可以看到每个数组下标的
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 呢？
若是按照树结构来找：
- 先找节点 6 的父节点 6 - lowestbit(6) = 4
- 找节点 4 的父节点 4 + lowestbit(4) = 8
- 找节点 8 的父节点 8 + lowestbit(8) = 16
- 共找到节点 4 8 16 三个节点
- 其中节点 6 在节点 4 的右子树中，所以节点 4 是不包含节点 6 的
- 节点 6 在节点 8 16 的左子树中，包含节点 6
- 所以更新节点 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] 即可。
