二叉索引树

二叉索引树(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

                o                ├ 1000 = 8
        ┌───────┴───────┐        │
        o               o        ├ 100  = 4
    ┌───┴───┐       ┌───┴───┐    │
    o       o       o       o    ├ 10   = 2
  ┌─┴─┐   ┌─┴─┐   ┌─┴─┐   ┌─┴─┐  │
  o   o   o   o   o   o   o   o  ├ 1    = 1
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5  │

我们看到二叉树不同层数二叉结尾是有规律的。例如第一层：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)
{
    return x&(-x);
}

建立索引

我们知道，索引的本质就是预先存储一些信息，现在我们来看如何从原数组 A 来构建我们的二叉索引数 BIT 。我们定义：

$$ BIT_i = \sum_{j = i - lowbit(i) + 1}^{i} A_j $$

看公式好像很复杂，我们拆解一下。看到下标 i - lowbit(i) + 1，我们知道代表了 i 所在节点左子树的底层节点。我们用图来说明如何计算 BIT[12] (图中标 x)

                o
        ┌───────┴───────┐
        o               x
    ┌───┴───┐       ┌───┴───┐
    o       o       x       o
  ┌─┴─┐   ┌─┴─┐   ┌─┴─┐   ┌─┴─┐
  o   o   o   o   x   x   o   o
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
A:                2 1 3 1
BIT:                   (7)

可以看到 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
        ┌───────┴───────┐
        x               o
    ┌───┴───┐       ┌───┴───┐
    x       x       o       o
  ┌─┴─┐   ┌─┴─┐   ┌─┴─┐   ┌─┴─┐
  x   x   x   x   o   o   o   o
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5

具体如何构建二叉索引树我们下面再说。

Sum

我们定义二叉查找树的查找操作为 sum(k) = A[1] + ... + A[k]，有了 BIT 之后，就可以这么求：

int sum(int k)
{
    int ans = 0;
    for (int i = k; i > 0; i = i-lowbit(i))
        ans += BIT[i];
    return ans;
}

还记得 n - lowbit(n) 代表什么吗？代表的是 n 节点的左祖父/父节点。因此为了求 sum(k) 我们只需要将 k 及 k 的所有左祖父/父节点相加即可。因此复杂度是 $O(\log n)$。

                                   lowbit

                o                ├ 1000 = 8
        ┌───────┴───────┐        │
        o               o        ├ 100  = 4
    ┌───┴───┐       ┌───┴───┐    │
    o       o       o       o    ├ 10   = 2
  ┌─┴─┐   ┌─┴─┐   ┌─┴─┐   ┌─┴─┐  │
  o   o   o   o   o   o   o   o  ├ 1    = 1
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5  │

我们以 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)
{
    for (int j = i; j <= MAX_N; j = j+lowbit(j))
        BIT[j] += delta;
}

可以看到，和 sum 类似，也是不断寻找祖父/父节点的过程，因此也是 $O(\log n)$。

初始化

可以有多种方式初始化，每种的复杂度不同。

先假设初始数组 A 全为 0，之后调用节点更新函数 edit 来更新数组中的每个元素，复杂度为 $O(n \log n)$。

void build()
{
    for (int i=1;i<=MAX_N;i++)
    {
        edit(i, A[i])
    }
}

当然初始化操作是可以达到 $O(n)$ 的。方法是像开头说的，先创建一个累加数组，于是只需要用 $O(1)$ 时间即可求得 A[j] - A[i]。

但这么做意义不是特别大。因为当我们采用 BIT 时，其实就意味着我们想利用它更新时间为 $O(\log n)$ 的特性，这意味着更新操作不会少。于是可以大胆猜测会有 $O(n)$ 个更新操作，这样整体的算法复杂度就要大于 $O(n \log n)$，那么强行用 $O(n)$ 来初始化 BIT 也没有太大的意义。

二叉索引树

使用场景