二叉索引树(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) 正好是父节点。再例如 1212 - lowbit(12) = 12 - 4 = 8 正好是 12 的父节点 8。而如果当前节点是父节点的左子树,则 n - lowbit(n) 代表了它的第一个"左祖父节点",例如节点 1010 - lowbit(10) = 10 - 2 = 8,是 10 的左祖父节点。

同理, n + lowbit(n) 是“右”祖父节点。例如 44 + lowbit(4) = 4 + 4 = 84 的父节点;而 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) 我们只需要将 kk 的所有左祖父/父节点相加即可。因此复杂度是 $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 也没有太大的意义。

#参考文章