树状数组：Binary Indexed Tree / Fenwick Tree

树状数组能在 \(O(\log n)\) 时间内查询数组的前缀和、更新单个元素，只需要 \(O(n)\) 空间。关键是：每个节点保存一段多长的区间，查询和更新时又该跳到哪个节点？

源代码

简介

树状数组（Binary Indexed Tree，简称 BIT，也叫 Fenwick Tree）维护数组的前缀和，并支持给某个元素增加一个值。本文使用普通加法：sum(i) 返回 a[1] + ... + a[i]，add(i, v) 则让 a[i] 增加 v。

与线段树（迭代版）相比，树状数组直接查询的是前缀。对于加法，我们仍然可以用两个前缀的差查询任意区间 [l, r]：sum(r) - sum(l - 1)。如果换成其他运算，就需要检查相应的代数条件；仅有结合律并不能保证这套查询与更新代码仍然成立。

树状数组使用 n + 1 个数组位置，其中下标 0 不使用。迭代线段树通常使用 2*n 个位置，递归实现通常分配约 4*n 个位置；它们的空间复杂度都是 \(O(n)\)。

树状数组的两个核心操作是 sum 和 add。先看它们共同维护的区间结构，再看代码。

每个节点存储哪个区间？

沿用线段树配图的思路，把每个节点保存的区间和画在它覆盖的原数组区间上方。定义 lowbit(i) = i & -i：它取出二进制表示中最低位的 1 所对应的数值，也就是节点 i 覆盖的区间长度。

16 个树状数组节点的区间覆盖图，下方为原数组下标 1 到 16 — 每个横条代表一个存储的区间和。横条上的数字是 BIT 下标，横向跨度就是它覆盖的区间。

核心不变量是：tree[i] 保存 a[i - lowbit(i) + 1 ... i] 的和。这里 a 指原数组，tree 指树状数组的内部存储，也就是下方代码中的 A。图中的数字都是下标，不是数组元素的值，也不是区间和。

tree[6]：6 = 0b0110，因此 lowbit(6) = 2，保存 [5, 6] 的和。
tree[12]：12 = 0b1100，因此 lowbit(12) = 4，保存 [9, 12] 的和。
tree[8]：8 = 0b1000，因此 lowbit(8) = 8，保存 [1, 8] 的和。

与完整的线段树不同，树状数组不会在每次划分时同时存储左右两半。例如，它保存 [1, 8] 的和，却没有单个节点保存 [9, 16] 的和。它在每个下标处存储一个以该下标为右端点的区间，再通过二进制表示确定区间之间的跳转。图中用 n = 16 展示规律，但数组长度并不要求是 2 的幂。

`add`：给一个元素增加一个值

1
2
3
void add(int i, T v) {  // 原数组 a[i] 增加 v；A 是 BIT 的内部存储
    while (i <= n) A[i] += v, i += i & -i;
}

更新一个元素时，必须修改所有包含这个下标的已存储区间。对于 add(5, Δ)，这些区间是 [5, 5]、[5, 6]、[1, 8] 和 [1, 16]。

单点更新依次访问 5、6、8、16，高亮的四个区间恰好都包含下标 5 — 更新 a[5] 时，四个高亮的区间和都要增加 Δ；它们都包含下标 5。

i += lowbit(i) 跳到下一个包含当前区间的更大区间。在二进制中，加上最低位的 1 所对应的值会向更高位进位：0101 → 0110 → 1000 → 10000。新区间的右端点向右移动，而左端点保持不变或向左移动，所以仍然包含被更新的元素。两次跳转之间被略过的节点不包含这个元素。

当 n = 16 时，循环依次访问 5 → 6 → 8 → 16，给每个节点保存的和增加 Δ；下一步得到 32，超出数组长度，循环结束。数组下标从 1 开始，A[0] 不使用。add 要求 1 <= i <= n；若从 0 开始，lowbit(0) = 0，循环就无法前进。

`sum`：查询前缀和

1
2
3
4
5
T sum(int i) {  // 原数组 a[1 ... i] 的前缀和；A 是 BIT 的内部存储
    T v{};
    while (i) v += A[i], i -= i & -i;
    return v;
}

查询前缀时，先取以 i 为右端点的区间，再接着查询它左边剩余的前缀。当前区间从 i - lowbit(i) + 1 开始，因此剩余前缀的右端点就是 i - lowbit(i)。这正是循环每次减去 lowbit(i) 的原因。

前缀查询路径为 13 到 12 到 8 到 0，读取的区间分别为 13、9 到 12、1 到 8 — sum(13) 读取节点 13、12、8。它们覆盖的区间无重叠、无遗漏地拼成 [1, 13]。

以 sum(13) 为例：

当前 `i`	`lowbit(i)`	读取的区间	下一个 `i`
13（`1101`）	1	`tree[13]`：`[13, 13]`	12
12（`1100`）	4	`tree[12]`：`[9, 12]`	8
8（`1000`）	8	`tree[8]`：`[1, 8]`	0（结束）

因此 sum(13) = tree[13] + tree[12] + tree[8]。代入一个具体数组检验：若 a[i] = i，这三个节点保存的和分别是 13、42、36，相加得到 91，恰好等于整数 1 到 13 的和。

每减去一次 lowbit，就清除一个二进制位上的 1：1101 → 1100 → 1000 → 0000。所以查询访问的节点数恰好等于下标中 1 的个数，最多为 \(O(\log n)\)。更新时，最低位的 1 则在每次跳转后移到更高位，因此更新也是 \(O(\log n)\)。sum 要求 0 <= i <= n；sum(0) 返回 0，所以即使 l = 1，区间查询公式也仍然适用。

C++ 模板

源代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
#include <vector>

template <typename T>
class fenwick {
public:
  int n;
  std::vector<T> A;
  fenwick(int n): n(n), A(n+1) {} // A[0] 不使用
  T sum(int i) {  // 原数组 a[1 ... i] 的前缀和
    T v{};
    while (i) v += A[i], i -= i & -i;
    return v;
  }
  void add(int i, T v) {  // 原数组 a[i] 增加 v
    while (i <= n) A[i] += v, i += i & -i;
  }
};

构造函数把所有已存储的区间和初始化为 0。若要从已有数组构建树状数组，可以对每个下标 1 ... n 调用 add(i, a[i])；这种简单构建方法耗时 \(O(n\log n)\)。若要把元素赋值为新值，而非增加一个差值，就保留原数组的值，先调用 add(i, new_value - a[i])，再更新 a[i]。数值类型要能够容纳所有中间结果，例如整数和可能超过 int 时使用 long long。

参考资料

Wikipedia：Fenwick Tree