FenwickTree [二叉索引树]

# 介绍

树状数组或二元索引树（英语：Binary Indexed Tree），又以其发明者命名为 Fenwick 树。其初衷是解决数据压缩里的累积频率（Cumulative Frequency）的计算问题，现多用于高效计算数列的前缀和，区间和。它可以在 $O(log n)$ 的时间内得到数组的前缀和 $(A[1] + A[2] + … + A[i])$ ，且在 $O(log n)$ 时间内支持动态修改数组的值。

# 使用场景

首先我们考虑一个数组 $A$ ，想求 $Ai,Ai+1,…,Aj$ 的和，如果只求一次，很自然地把这些数相加即可，时间复杂度为 $O(n)$ 。但现在如果我们经常要求 $A$ 中第 $i$ 到第 $j$ 个元素的和，则最好事先做个索引。

做法也简单，我们新建一个数组 $C$ ，数组 $C$ 中的元素 $Ci=A0+A1+…+Ai$ 。于是如果我们要求 $Ai$ 到 $Aj$ 的和，则有 $Q(i,j)=Ai+…+Aj=Cj−Ci−1$ 。即通过访问数组 $C$ ，我们只需要 $O(1)$ 的时间即可。

但如果 $A$ 中的元素 $Ai$ 的值有变化呢？这时，我们需要更新 $Ci$ 之后的所有数据，需要 $O(n)$ 的时间。

于是索引 C 需要空间 $O(n)$ ，访问 $O(1)$ ，修改 $O(n)$ 。

有时我们需要平衡索引的访问和修改时间，二叉索引数 (binary indexed tree) 可以让我们用 O (logn) O (log⁡n) 的时间复杂度进行访问，用 $O(logn)$ 完成修改。虽然称为 "树"，但其实是用数组实现的。

# 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
2
3
4
5
6
7
8
9
10

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

1
2
3
4

# 建立索引

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

$B I T_i=\sum_{j=i-l o w b i t(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)

1
2
3
4
5
6
7
8
9
10

可以看到 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

1
2
3
4
5
6
7
8
9

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

# 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;
}

1
2
3
4
5
6
7

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

                                   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
2
3
4
5
6
7
8
9
10

我们以 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;
}

1
2
3
4
5

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

# 初始化

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

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

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

1
2
3
4
5
6
7

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

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

# 演示

# 实现

# JavaScript

/*
 * Author: Mohit Kumar
 * Fedwick Tree Implementation in JavaScript
 * Fedwick Tree Implementation for finding prefix sum.
*/

class FenwickTree {
  constructor (feneickArray, array, n) {
    for (let i = 1; i <= n; i++) {
      feneickArray[i] = 0
    }
    for (let i = 0; i < n; i++) {
      this.update(feneickArray, n, i, array[i])
    }
  }

  update (feneickArray, n, index, value) {
    index = index + 1
    while (index <= n) {
      feneickArray[index] += value
      index += index & (-index)
    }
  }

  getPrefixSum (feneickArray, index) {
    let currSum = 0
    index = index + 1
    while (index > 0) {
      currSum += feneickArray[index]
      index -= index & (-index)
    }

    return currSum
  }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

注意，feneickArray 是从 1 开始的。

# 参考

编辑

上次更新: 2022/10/19, 17:35:33

← DepthFirstSearch [二叉树的深度优先遍历] Abs [绝对值]→