引入

有这样一类问题：维护一个长度为 n 的序列，需要支持两种操作：

  1. 单点修改某个位置的值。
  2. 查询一个前缀和，或者区间和。

如果每次修改后都重新求和，复杂度会很难看。朴素做法单次查询是 O(n)，如果操作很多就会超时。

这时候就需要 树状数组（Binary Indexed Tree，简称 BIT）。

它可以在 O(log n) 的时间内完成单点修改和前缀和查询，代码短，常数也小，是竞赛里非常常见的数据结构。

lowbit

树状数组最核心的东西就是 lowbit。

1
2
3
int lowbit(int x) {
  return x & -x;
}

lowbit(x) 表示 x 的二进制表示中，最低位的 1 以及它所代表的值。

例如：

  • lowbit(6) = 2，因为 6 = (110)2
  • lowbit(8) = 8，因为 8 = (1000)2
  • lowbit(12) = 4，因为 12 = (1100)2

这个东西决定了树状数组中每个位置管辖的区间长度。

基本思想

设树状数组数组为 c[i]，它维护一段区间和：

也就是说，c[i] 存的是一个以 i 为右端点，长度为 lowbit(i) 的区间和。

例如当 n = 8 时：

  • c[1] 维护 [1, 1]
  • c[2] 维护 [1, 2]
  • c[3] 维护 [3, 3]
  • c[4] 维护 [1, 4]
  • c[5] 维护 [5, 5]
  • c[6] 维护 [5, 6]
  • c[7] 维护 [7, 7]
  • c[8] 维护 [1, 8]

看起来有点奇怪，但正是这种分块方式，让我们能高效地跳来跳去。

前缀和查询

查询前缀和 时，只需要不断减去 lowbit(x)：

1
2
3
4
5
6
7
8
int query(int x) {
  int res = 0;
  while (x) {
    res += c[x];
    x -= lowbit(x);
  }
  return res;
}

为什么这样是对的？

因为每次取出的 c[x] 都对应一段以 x 结尾的区间，然后跳到前一个还没统计的位置。这样取到的若干段区间恰好不重不漏地覆盖整个前缀 [1, x]。

例如查询 sum(13)：

  • 先加上 c[13]，维护区间 [13, 13]
  • 跳到 12，加上 c[12]，维护区间 [9, 12]
  • 跳到 8，加上 c[8]，维护区间 [1, 8]

合起来正好是 [1, 13]。

单点修改

如果把 a[x] 加上一个值 v，那么所有包含位置 x 的 c[i] 都要加上 v。

更新方式是不断加上 lowbit(x)：

1
2
3
4
5
6
void add(int x, int v) {
  while (x <= n) {
    c[x] += v;
    x += lowbit(x);
  }
}

这也是树状数组最妙的地方之一：

  • 查询时往前跳：x -= lowbit(x)
  • 修改时往后跳：x += lowbit(x)

区间和查询

如果要求区间 [l, r] 的和，只需要转化为两个前缀和：

所以：

1
2
3
int rangeQuery(int l, int r) {
  return query(r) - query(l - 1);
}

完整模板

例题：洛谷 P3374 【模板】树状数组 1。

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
36
37
38
39
40
41
42
#include <bits/stdc++.h>

const int N = 5e5 + 10;
int n, m;
int c[N];

int lowbit(int x) {
  return x & -x;
}

void add(int x, int v) {
  while (x <= n) {
    c[x] += v;
    x += lowbit(x);
  }
}

int query(int x) {
  int res = 0;
  while (x) {
    res += c[x];
    x -= lowbit(x);
  }
  return res;
}

int main() {
  std::cin.tie(0)->sync_with_stdio(0);
  std::cin >> n >> m;
  for (int i = 1, x; i <= n; ++i) {
    std::cin >> x;
    add(i, x);
  }
  while (m--) {
    int op, x, y;
    std::cin >> op >> x >> y;
    if (op == 1) add(x, y);
    else std::cout << query(y) - query(x - 1) << '\n';
  }
  std::cout.flush();
  return 0;
}

复杂度分析

无论是 add 还是 query，每次都会跳掉一个 lowbit，因此复杂度都是 O(log n)。

空间复杂度为 O(n)。

树状数组和线段树的区别

树状数组和线段树都能维护区间信息，但两者还是有区别的。

树状数组优点

  • 代码短
  • 常数小
  • 写起来不容易错

树状数组缺点

  • 功能相对单一
  • 一般更适合维护“可差分、可前缀合并”的信息，比如和、计数之类
  • 遇到复杂区间操作通常不如线段树灵活

所以如果只是单点修改 + 区间求和，树状数组一般比线段树更舒服。

扩展：区间修改

树状数组最基础的是单点修改、前缀查询。

但通过差分，也可以做到：

  • 区间修改，单点查询
  • 区间修改，区间查询

区间修改，单点查询

对差分数组做树状数组。

如果要给区间 [l, r] 都加上 v，那么只需要：

  • add(l, v)
  • add(r + 1, -v)

最后某个点 x 的值就是差分数组前缀和。

区间修改，区间查询

这个需要维护两个树状数组，属于经典结论。

若差分数组为 b，则原数组前缀和可写成：

因此维护两个 BIT 即可。

这部分模板比较固定，比赛里记结论就行。

应用

树状数组除了维护区间和，还有很多常见用途：

  • 求逆序对
  • 维护前缀最大值（某些特殊情况下）
  • 离散化后做计数
  • 配合扫描线处理二维偏序问题

尤其是逆序对，几乎是树状数组入门必做题。

总结

树状数组本质上是一个利用二进制性质维护前缀信息的数据结构。

它的重点其实就两句话：

  • 查询前缀和时，不断 x -= lowbit(x)。
  • 单点修改时，不断 x += lowbit(x)。

如果你第一次学线性数据结构维护区间信息，我会建议先学树状数组，再学线段树。因为树状数组更像一个精巧的小工具，而线段树更像一把瑞士军刀。

前者短小好写，后者功能全面。