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

> [源代码](https://github.com/sky-bro/AC/tree/master/Algorithms/BIT)

<!--more-->

## 简介

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

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

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

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

## 每个节点存储哪个区间？

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

{{< figure src="/images/posts/fenwick-tree/stored-intervals.svg" caption="每个横条代表一个存储的区间和。横条上的数字是 BIT 下标，横向跨度就是它覆盖的区间。" alt="16 个树状数组节点的区间覆盖图，下方为原数组下标 1 到 16" >}}

核心不变量是：**`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`：给一个元素增加一个值

```cpp
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]`。

{{< figure src="/images/posts/fenwick-tree/point-update.svg" caption="更新 a[5] 时，四个高亮的区间和都要增加 Δ；它们都包含下标 5。" alt="单点更新依次访问 5、6、8、16，高亮的四个区间恰好都包含下标 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`：查询前缀和

```cpp
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)` 的原因。

{{< figure src="/images/posts/fenwick-tree/prefix-query.svg" caption="sum(13) 读取节点 13、12、8。它们覆盖的区间无重叠、无遗漏地拼成 [1, 13]。" alt="前缀查询路径为 13 到 12 到 8 到 0，读取的区间分别为 13、9 到 12、1 到 8" >}}

以 `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++ 模板

> [源代码](https://github.com/sky-bro/AC/tree/master/Algorithms/BIT)

```cpp
#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](https://en.wikipedia.org/wiki/Fenwick_tree)