二叉索引树(Binary Indexed Tree) 也称为 Fenwick tree，中文也称树状数组。它可以在 O(log n) 的时间内得到数组的前缀和(A[1] + A[2] + … + A[i])，且在 O(log n) 时间内支持动态修改数组的值。
使用场景
首先我们考虑一个数组 A，想求 $A_i, A_{i+1}, …, A_j$ 的和，如果只求一次，很自然地把这些数相加即可，时间复杂度为 $O(n)$。但现在如果我们经常要求 A 中第
i 到第 j 个元素的和，则最好事先做个索引。
做法也简单，我们新建一个数组 C，数组 C 中的元素 $C_i = A_0 + A_1 + … + A_i$。于是如果我们要求 $A_i$ 到 $A_j$ 的和，则有 $Q(i, j) = A_i + … + A_j = C_j - C_{i-1}$。即通过访问数组 C，我们只需要 $O(1)$ 的时间即可。
但如果 A 中的元素 $A_i$ 的值有变化呢？这时，我们需要更新 $C_i$ 之后的所有数据，需要 $O(n)$ 的时间。
于是索引 C 需要空间 $O(n)$，访问 $O(1)$，修改 $O(n)$。
二叉索引树
有时我们需要平衡索引的访问和修改时间，二叉索引数 (binary indexed tree) 可以让我们用 $O(\log n)$ 的时间复杂度进行访问，用 $O(\log n)$ 完成修改。虽然称为"树"，但其实是用数组实现的。
Lowbit
首先，我们来看一个完全二叉树：
lowbit |
我们看到二叉树不同层数二叉结尾是有规律的。例如第一层：1, 3, 5, 7, …，这些数的二进制分别是 1, 11, 101, 111, …，最后一位都是 1。同理，第二层的数都以 10 结尾。现在我们定义一个新的函数 lowbit(n)，它的作用是在 n 的二进制上从右往左数，数到第一个 1 为止。例如数字 6 的二进制是 110，向右数到第一个 1，得到 10，得到 lowbit(6) = b10 = 2，同理 lowbit(12) = 4。
那么 lowbit 有什么用呢？如果当前节点是父节点的右子树，则 n - lowbit(n)
正好是父节点。再例如 12，12 - lowbit(12) = 12 - 4 = 8 正好是 12
的父节点 8。而如果当前节点是父节点的左子树，则 n - lowbit(n)
代表了它的第一个"左祖父节点"，例如节点 10，10 - lowbit(10) = 10 - 2 = 8，是 10 的左祖父节点。
同理， n + lowbit(n) 是“右”祖父节点。例如 4，4 + lowbit(4) = 4 + 4 = 8
是 4 的父节点；而 6 + lowbit(6) = 6 + 2 = 8 则对应于 6 的右祖父节点。
同时可以看到 n - lowbit(n) + 1 在完全二叉数上对应的节点，就是从数字 n
对应的节点开始，不断取节点的左子节点直到第一层的那个节点。例如 12
所在的结点，不断取左子节点，最终得到的是 9，而 9 = 12 - 4 + 1 = 12 - lowbit(12) + 1。
有了 lowbit，我们就能在完全二叉树里快速地定位：
n - lowbit(bit)为左祖父/父节点n + lowbit(bit)为右祖父/父节点n - lowbit(bit) + 1为左子树的底层节点
从编程的角度上， lowbit 可以由位运算完成 (C++)：
int lowbit(int x) |
建立索引
我们知道，索引的本质就是预先存储一些信息，现在我们来看如何从原数组 A 来构建我们的二叉索引数 BIT 。我们定义：
$$ BIT_i = \sum_{j = i - lowbit(i) + 1}^{i} A_j $$
看公式好像很复杂，我们拆解一下。看到下标 i - lowbit(i) + 1，我们知道代表了
i 所在节点左子树的底层节点。我们用图来说明如何计算 BIT[12] (图中标 x)
o |
可以看到 12 - lowbit(12) + 1 = 12-4+1=9，因此 BIT[12] = A[9] + A[10] + A[11] + A[12]。同理，如果要计算 BIT[8]，则需要计算 A[1] + ... + A[8]，因为 8 - lowbit(8) + 1 = 1。
x |
具体如何构建二叉索引树我们下面再说。
Sum
我们定义二叉查找树的查找操作为 sum(k) = A[1] + ... + A[k]，有了 BIT
之后，就可以这么求：
int sum(int k) |
还记得 n - lowbit(n) 代表什么吗？代表的是 n 节点的左祖父/父节点。因此为了求
sum(k) 我们只需要将 k 及 k 的所有左祖父/父节点相加即可。因此复杂度是
$O(\log n)$。
lowbit |
我们以 6 为例，BIT[6] 相当于 A[5] + A[6]，但我们要计算 A[1] + ... + A[6]，因此还要计算 A[1] + ... + A[4]，而在 BIT 中，这正好对应于 BIT[4]。再以 14 为例，BIT[14] = A[13] + a[14]，还差 A[1] + ... + A[12]，于是找到
14 - lowbit(14) = 14 - 2 = 12，而由于 BIT[12] = BIT[9] + ... + BIT[12]，因此还差 A[1] + ... + A[8]，正好对应于 BIT[8]，而又有 12 - lowbit(12) = 12 - 4 = 8 。
所以说 sum(k) 操作就是求节点 k 及它的父节点的和。
更新节点
如果 A[k] 的值发生变化了怎么办？从 BIT 的定义可知，A[k] 的值会影响 k 的所有右祖父/父节点。而这可以通过 k + lowbit(k) 来得到。例如 A[9]
发生了变化，根据定义，我们需要更新 BIT[9], BIT[10], BIT[12]。代码如下：
void edit(int i, int delta) |
可以看到，和 sum 类似，也是不断寻找祖父/父节点的过程，因此也是 $O(\log n)$。
初始化
可以有多种方式初始化，每种的复杂度不同。
先假设初始数组 A 全为 0，之后调用节点更新函数 edit 来更新数组中的每个元素，复杂度为 $O(n \log n)$。
void build() |
当然初始化操作是可以达到 $O(n)$ 的。方法是像开头说的，先创建一个累加数组，于是只需要用 $O(1)$ 时间即可求得 A[j] - A[i]。
但这么做意义不是特别大。因为当我们采用 BIT 时，其实就意味着我们想利用它更新时间为 $O(\log n)$ 的特性，这意味着更新操作不会少。于是可以大胆猜测会有 $O(n)$ 个更新操作，这样整体的算法复杂度就要大于 $O(n \log n)$，那么强行用 $O(n)$ 来初始化 BIT 也没有太大的意义。