线段树与树状数组：区间查询与区间修改怎么选

发表于 分类于
从区间加加区间和这一道题出发，讲透树状数组与线段树的取舍、懒标记原理、代码量与常数的真实差距。

很多同学学完数据结构的第一反应是：”线段树是万能的，区间问题全上线段树就行。”

这个判断在 CSP-J T3 也许能拿满分，但在 CSP-S T3/T4 上，一份常数过大的线段树会直接 TLE。而换成树状数组，同样的题代码量只有三分之一。

这篇文章不打算罗列两者的功能清单，而是拿同一道题——“区间加 + 区间求和”——分别用树状数组和线段树写一遍，让你亲眼看到：同一个任务，两种数据结构的代码量和常数差多少，以及为什么。

问题背景

我们维护一个长度为 n 的数组 a，初始全为 0，需要支持两种操作：

  1. add(l, r, v)：把区间 [l, r] 内每个数加上 v
  2. query(l, r)：查询区间 [l, r] 的和

n = 10^6，q = 10^5。这是一道标准的”区间修改 + 区间查询”题，正好用来对比两种数据结构。

先说清楚复杂度目标：这两种操作都要做到 O(log n)。如果一次操作是 O(n)，q = 10^5 就是 10^11 次运算，必挂。

树状数组与线段树结构对照

思路

第一步：树状数组到底能做什么

树状数组（Binary Indexed Tree）的核心只有一句话：用 lowbit 维护前缀和，让”单点修改”和”前缀查询”互为对方的逆操作。

lowbit(i) = i & (-i)，即 i 的二进制最低位 1 对应的值。比如 lowbit(12) = 4，lowbit(7) = 1。

树状数组的定义是：tree[i] 存储的是 a[i - lowbit(i) + 1 ... i] 这一段的和。

有了这个定义，两个操作就非常自然了：

前缀和 sum(x)：不断累加 tree[x]，然后 x -= lowbit(x)。

为什么正确？以 x = 13 为例：13 的 lowbit 是 1，所以取 tree[13]（管 a[13]），然后 x = 12，lowbit(12) = 4，取 tree[12]（管 a[9..12]），然后 x = 8，lowbit(8) = 8，取 tree[8]（管 a[1..8]），x = 0 结束。这三段不重不漏地拼成了 a[1..13]。

1
for (int i = x; i > 0; i -= i & (-i)) res += tree[i];

单点修改 add(x, v)：不断让 x += lowbit(x)。

为什么正确？把所有”管辖范围包含位置 x”的结点都更新一遍。tree[13]、tree[12]、tree[8] 恰好就是那些。沿 lowbit 往上跳不会漏。

1
for (int i = x; i <= n; i += i & (-i)) tree[i] += v;

区间和：前缀和相减，sum(r) - sum(l - 1)。O(log n)。

到这里为止，一切都很干净。树状数组的强项是：单点改 + 前缀和 = O(log n)，区间和是白送的减法。

第二步：为什么”区间修改”用树状数组很别扭

现在问题来了：如何支持 add(l, r, v)？

直觉想法是：把 [l, r] 里的每个元素都单点修改一遍。那是 O(n log n)，白做了。

经典做法：开两棵树状数组（也叫”差分 + 树状数组”）。

先在脑子里把 a 数组做一次差分：d[i] = a[i] - a[i-1]（a[0] = 0）。

差分有个漂亮的性质：区间加变成了两次单点修改。

因为 a[l..r] 每个数都加 v，等价于 d[l] += v，而 r+1 处要抵消：d[r+1] -= v。

就像一排身高，1 号到 5 号都长高了 5cm，那么第 1 人的”身高差”多了 5，第 6 人的”身高差”就少了 5。

于是我们只要用两棵树状数组分别维护 d[i] 和 i * d[i]。

关键推导：原数组的前缀和

1
2
3
4
5
sum(x) = a[1] + a[2] + ... + a[x]
       = Σ_{i=1..x} Σ_{j=1..i} d[j]        // 把 a[i] 展开成差分的前缀和
       = Σ_{j=1..x} d[j] * (x - j + 1)      // 交换求和顺序：d[j] 被累计了 x-j+1 次
       = (x+1) * Σ_{j=1..x} d[j] - Σ_{j=1..x} j*d[j]   // 把 x-j+1 拆成 (x+1)-j
       = (x+1) * query(bit1, x) - query(bit2, x)

注意最后一步是 x+1 而不是 x。 这是这个公式最容易错的一个字符：x - j + 1 拆成 (x+1) - j，多出来的那个 1 藏在系数里。写成 x * Σd[j] - Σj·d[j] 会恒定少算 Σd[j]，用上面的例子一测就露馅。

所以维护两棵 BIT：一棵存 d[i]，一棵存 i*d[i]。区间和就是两次前缀查询相减：

1
query(l, r) = calc(r) - calc(l-1)，其中 calc(x) = (x+1) * sum(bit1, x) - sum(bit2, x)

这里的坑（学生最容易错的地方）：

  • 坑 1：必须开 long long。 i * d[i] 里 i 最大到 10^6，d[i] 的绝对值可能累加到很大，乘积轻易超过 int。而且 (x+1) * Σd[j] 这一项会达到 n^2 * v 的量级（10^12 × v），int 溢出是必然的。
  • 坑 2：r = n 时不需要 d[n+1] -= v。 但你的 BIT 循环是 i <= n，如果你不加判断而写了 for (i = r+1; i <= n; ...)，在 r=n 时循环体自然不执行，是安全的；但如果你为了别的理由写了 add(r+1, ...) 且没有上界判断，就会越界。
  • 坑 3：区间和公式的符号容易搞错。 建议把它封装成一个 prefixSum(x) 函数，然后 rangeSum(l,r) = prefixSum(r) - prefixSum(l-1)，把易错的部分只写一遍。
  • 坑 3.5：别把 x+1 写成 x。 见上面的推导。用 n=3、add(2,3,5) 手算一遍：a = [0,5,5]，sum(3) = 10。此时只有 d[2] = 5，所以 Σd[j] = 5、Σj·d[j] = 10，(3+1)*5 - 10 = 10 ✓；写成 3*5 - 10 = 5 ✗，恰好少算了 Σd[j] = 5。
  • 坑 4：中途插入一个数导致后面所有下标平移 → 所有 d[i] 都变了，BIT 直接失效。这就是下面要讲的坐标压缩要解决的问题。

第三步：线段树的三类操作与懒标记

线段树的结点不再对应 lowbit 区间，而是对应一个明确的左右子树区间 [l, r]，mid = l + (r-l)/2。每个结点维护一个”信息”（区间和、区间最值等）。

线段树的三类基本操作：

操作描述时间
单点修改走到叶子，改叶子，回溯更新O(log n)
区间查询把 [l, r] 拆成若干完整结点，取信息合并O(log n)
区间修改命中完整结点就”打标记”返回，部分相交就递归O(log n)

为什么区间查询是 O(log n)？ 因为 [l, r] 在任何一层最多只有 2 个结点是”部分相交”的（一个在中点左边，一个在中点右边），其余都是完整命中并立即返回。所以访问的结点总数是 O(log n) 级别，不是 O(n)。

懒标记（lazy tag）的原理：

朴素做法是”区间改 = 把区间内每个叶子都改一遍”，O(n)。但注意：如果一个结点管辖的整个区间都要加 v，那么它的所有后代在逻辑上也都加了 v。既然我们暂时不需要立刻知道每个叶子的值，就可以只在这个结点记一笔账 lazy += v，然后直接返回，不往下走。

查询的时候，如果需要进入一个带 lazy 的结点的孩子，就要把这笔账”下推”：

1
2
3
4
5
6
7
8
void pushdown(int p) {
    if (lazy[p] == 0) return;
    tree[p<<1]   += lazy[p] * (mid - l + 1);   // 左孩子长度
    lazy[p<<1]   += lazy[p];
    tree[p<<1|1] += lazy[p] * (r - mid);       // 右孩子长度
    lazy[p<<1|1] += lazy[p];
    lazy[p] = 0;
}

这里有一个最容易错的细节：下传给左孩子的是 lazy * 左区间长度，不是 lazy 本身。因为结点存的是区间和！如果结点存的是最值，那才直接传 lazy。

一句话总结 pushdown 的意义：保证”什么时候访问孩子，什么时候把父亲的账结清”，这样结点值永远是最新的。

第四步：同一道题，两份代码对比

任务：add(l,r,v) + query(l,r)。

树状数组版（两个 BIT）核心只有四个函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 在差分数组的 x 处加 v（等价于原数组 a[x..n] 全部加 v）
void addDiff(int x, ll v) {
    for (int i = x; i <= n; i += i & (-i)) {
        t1[i] += v;
        t2[i] += v * x;
    }
}
// 区间加 = 两次差分修改
void rangeAdd(int l, int r, ll v) { addDiff(l, v); addDiff(r + 1, -v); }
// 原数组前 x 项的和 = (x+1) * Σd[j] - Σ(j*d[j])，两棵树状数组都要遍历累加
ll prefixSum(int x) {
    ll s1 = 0, s2 = 0;
    for (int i = x; i > 0; i -= i & (-i)) { s1 += t1[i]; s2 += t2[i]; }
    return (x + 1) * s1 - s2;
}
// 区间和 = 两次前缀和相减
ll rangeSum(int l, int r) { return prefixSum(r) - prefixSum(l - 1); }

线段树版需要 build（建树）、pushdown（下传懒标记）、update（区间加）、query（区间查）四个函数，而且 update 和 query 都必须正确处理「完全命中/不相交/只递归左孩子/只递归右孩子/递归两个孩子」五种情况。

代码量对比（含注释与空行）：树状数组约 40 行，线段树约 75 行。差距主要来自：递归的双参数边界传递、pushdown、build，以及那几种递归分支的组合。完整可提交代码见「参考代码」一节。

第五步：内存与常数的真实差距

这是学生最关心的”到底差多少”，我给你量化的结论（n = 10^6，long long）：

树状数组（2 棵）线段树
数组大小2 × 8n = 16 MB2 × 8 × 4n = 64 MB
递归深度0（无递归）~20 层
单次区间改约 2 × log n 次循环，无函数调用约 4log n 个结点访问，含递归调用
单次区间查约 2 × 2log n 次循环约 4log n 个结点访问

内存：线段树是树状数组的 4 倍。这在 128MB 限制下可能直接超了（64MB + 其他数组），而树状数组只占 16MB 非常安全。

常数：线段树每次操作有递归函数调用的开销（栈帧压栈、传参、返回）。经验值是树状数组比线段树快 2～4 倍。在 CSP-S T4 那种需要卡常的场景，这个差距就是 AC 和 TLE 的差别。

所以结论是：只要树状数组能做，就用树状数组。 只有当树状数组做不到时，才上树状数组的扩展或线段树。

第六步：坐标压缩在区间修改问题里的作用

回到坑 4：如果操作里有”在位置 p 插入一个数”或者”值域可能达到 10^9”，怎么办？

值域很大 → 离散化。 离线读入所有操作，把所有出现过的位置/坐标收集起来排序去重，映射到 1..k。区间加区间和只关心”哪些位置被覆盖”，不关心坐标的实际大小，所以离散化完全无损。前提：所有操作必须离线读入（这就是为什么这类题常常不能在线）。

有插入操作 → 平衡树 / 树套树 / 离散化 + “插入转赋值”。 典型做法：把插入操作离线收集，最终确定每个元素的真实位置（因为每个位置被插入的时刻是已知的），然后按最终顺序离散化；插入本身用”赋值”处理（该位置此前是空的，相当于 0），插入前的所有操作实际上不影响这个位置。这种”离线确定位置 + 在线按时刻赋值”的手法在 NOI 级题目里非常常见。

注意：离散化会改变 lowbit 的分布，所以离散化之后必须重新构建树状数组或线段树，不能在原结构上改。

第七步：什么时候必须用线段树

以下场景，树状数组做不到或代价过高，应该用线段树：

  1. 维护区间最值：区间加、区间最大值。差分对 max 没有可加性——Σd[i] 变成 max 完全没有意义。带懒标记的线段树是标准解法。
  2. 维护”有结合律但差分后丢失语义”的信息：区间 gcd、矩阵乘法、字符串哈希（区间合并 hash = h_left * base^len_right + h_right）、区间异或（异或其实可以 BIT 维护）等。差分只对”可加/可减”的代数信息有效。
  3. 需要区间修改 + 复杂合并：区间赋值 + 区间求和（注意这也不能用差分 BIT 简单做，因为赋值的差分形式与位置有关，必须记录修改点数量）。
  4. 在线算法：题强制在线（^ last_ans 强制解密）时无法离线离散化，线段树更通用。
  5. 需要维护修改历史 / 可回滚：如”区间加 + 区间历史最值”，只能线段树挂时间维度。

选型口诀：先问自己”这个问题能不能写成差分/前缀形式”。能 → BIT（还能省一半常数和时间）；不能 → 线段树。

正确性

以线段树模板为例说明为什么它是对的：

  • build：叶子存 a[i]，非叶子存左右孩子之和。由归纳法，任意结点 sum 等于其区间内元素之和。初始全 0 的场景可以省略 build。
  • update(p, l, r, L, R, v)：
    • 若 [l,r] ⊆ [L,R]，执行 sum[p] += (r-l+1)*v; lazy[p] += v; return;。此时逻辑上区间内每个元素确实都加了 v，且该信息已记录（sum 立即正确，lazy 记录待下传的部分），正确。
    • 若不相交，return，不影响。
    • 否则先 pushdown（把祖先欠的账结清，使孩子值可信），再递归左右孩子，最后 sum[p] = sum[2p] + sum[2p+1]。由归纳，两个孩子正确则父亲正确。
  • query(p,l,r,L,R)：不相交返回 0；完全覆盖返回 sum[p]（此时该结点的账已由 update 保证正确，部分覆盖时也经过 pushdown）；否则 pushdown 后递归求和。由归纳，返回值等于 [L,R] 内的真实元素和。
  • pushdown 的必要性：若不 pushdown 就去读孩子的 sum，读到的是过期值。pushdown 后孩子 sum 与 lazy 恰好反映父亲懒标记的全部内容，且父亲 lazy 归零（防止重复下传），所以不变量”每个结点的 sum 永远包含它自己及所有祖先未下传的贡献”始终成立。

树状数组版正确性由前面第二节的推导给出：sum(x) = (x+1)·Σd[j] − Σj·d[j]，两次差分修改（d[l] += v、d[r+1] -= v）等价于一次区间加。

复杂度

操作树状数组(2棵)线段树
单点加O(log n)O(log n)
区间加O(log n)O(log n)
前缀和O(log n)O(log n)
区间和O(log n)O(log n)
空间16n 字节64n 字节
实测常数基准 1×约 2～4×

两者渐进复杂度相同，差别在常数与内存。这是典型的”选对了就过、选错了就 TLE”的场景。

参考代码（C++17）

线段树模板：区间加 + 区间和 + 懒标记，可直接提交。

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

class SegmentTree {
private:
    int n;
    vector<ll> sum_, lazy_;   // 用 vector 支持任意 n；sum_ 存区间和，lazy_ 存待下传增量

    // 懒标记下推：把本结点欠的账结清到两个孩子
    // 关键：sum_ 存的是"区间和"，所以要乘以孩子区间的长度
    void pushdown(int p, int l, int r) {
        if (lazy_[p] == 0) return;
        int mid = l + (r - l) / 2;
        ll v = lazy_[p];

        sum_[p << 1]     += v * (mid - l + 1);   // 左孩子区间 [l, mid]
        lazy_[p << 1]     += v;
        sum_[p << 1 | 1] += v * (r - mid);       // 右孩子区间 [mid+1, r]
        lazy_[p << 1 | 1] += v;

        lazy_[p] = 0;     // 必须清零，否则同一笔账会被重复下传
    }

    void build(int p, int l, int r, const vector<ll>& a) {
        if (l == r) { sum_[p] = a[l]; return; }
        int mid = l + (r - l) / 2;
        build(p << 1, l, mid, a);
        build(p << 1 | 1, mid + 1, r, a);
        sum_[p] = sum_[p << 1] + sum_[p << 1 | 1];
    }

    // 给 [L, R] 内每个元素加 v
    void update(int p, int l, int r, int L, int R, ll v) {
        if (L <= l && r <= R) {           // 当前结点区间被完全覆盖
            sum_[p] += v * (r - l + 1);  // 区间和增加 = v × 区间长度
            lazy_[p] += v;               // 打标记，不再往下走
            return;
        }
        pushdown(p, l, r);               // 只部分相交时才需要下推
        int mid = l + (r - l) / 2;       // 向下取整中点，避免 (l+r) 溢出
        if (L <= mid) update(p << 1, l, mid, L, R, v);
        if (R >  mid) update(p << 1 | 1, mid + 1, r, L, R, v);
        sum_[p] = sum_[p << 1] + sum_[p << 1 | 1];  // 回溯更新
    }

    // 查询 [L, R] 的区间和
    ll query(int p, int l, int r, int L, int R) {
        if (L <= l && r <= R) return sum_[p];   // 完全命中，直接取结点值
        pushdown(p, l, r);
        int mid = l + (r - l) / 2;
        ll ans = 0;
        if (L <= mid) ans += query(p << 1, l, mid, L, R);
        if (R >  mid) ans += query(p << 1 | 1, mid + 1, r, L, R);
        return ans;
    }

public:
    explicit SegmentTree(const vector<ll>& a) {
        n = (int)a.size() - 1;             // 数组从 1 开始编号
        sum_.assign(4 * n + 8, 0);
        lazy_.assign(4 * n + 8, 0);
        build(1, 1, n, a);
    }
    void range_add(int l, int r, ll v) { update(1, 1, n, l, r, v); }
    ll   range_sum(int l, int r)       { return query(1, 1, n, l, r); }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;

    vector<ll> a(n + 1, 0);              // 初始数组全为 0
    SegmentTree seg(a);

    while (q--) {
        int op, l, r;
        cin >> op >> l >> r;
        if (op == 1) {
            ll v;
            cin >> v;
            seg.range_add(l, r, v);
        } else {
            cout << seg.range_sum(l, r) << '\n';
        }
    }
    return 0;
}

对照：同一道题用两个树状数组怎么写

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
43
44
45
46
47
48
49
50
51
52
53
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int MAXN = 1000005;
int n;                        // 数组实际长度
ll t1[MAXN], t2[MAXN];        // t1 维护 d[i]，t2 维护 i * d[i]

// 在差分数组的 x 处加 v（等价于原数组 a[x..n] 全部加 v）
void addDiff(int x, ll v) {
    for (int i = x; i <= n; i += i & (-i)) {
        t1[i] += v;
        t2[i] += v * x;
    }
}

// 区间加 [l, r]：等价于 d[l] += v 且 d[r+1] -= v
// 当 r == n 时第二步不需要，addDiff 的循环上界 n 会自然跳过
void rangeAdd(int l, int r, ll v) {
    addDiff(l, v);
    addDiff(r + 1, -v);
}

// 原数组前 x 项的和：sum(x) = (x+1) * Σd[j] - Σ(j*d[j])
ll prefixSum(int x) {
    ll s1 = 0, s2 = 0;
    for (int i = x; i > 0; i -= i & (-i)) {
        s1 += t1[i];
        s2 += t2[i];
    }
    return (x + 1) * s1 - s2;
}

// 区间和：两次前缀和相减
ll rangeSum(int l, int r) {
    return prefixSum(r) - prefixSum(l - 1);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int q;
    cin >> n >> q;
    while (q--) {
        int op, l, r;
        ll v;
        cin >> op >> l >> r;
        if (op == 1) { cin >> v; rangeAdd(l, r, v); }    // op=1：区间加 v
        else         { cout << rangeSum(l, r) << '\n'; } // op=2：区间求和
    }
    return 0;
}

对比一下：线段树版 75 行（含注释），树状数组版 40 行。这就是”能翻译就用 BIT”的直接收益。

易错点清单

  1. int mid = (l + r) >> 1 在 l、r 接近 int 上界时会溢出。 统一写 int mid = l + (r - l) / 2;。本文所有代码都已按此写法。
  2. 懒标记下传时忘记乘区间长度。 结点存区间和，就必须乘；结点存最值（max/min），才直接加。
  3. 下传后忘记把 lazy 清零。 导致同一笔账被重复下传，答案成倍放大。
  4. sum 和 lazy 数组开成 4n 太小。 至少 4*n + 8。
  5. 全部用 int。 区间和、i*d[i]、(x+1)*Σd[j] 全部可能爆 int，一律 long long。
  6. 两个 BIT 写成 int 数组。 同上，t1、t2 都必须是 long long。
  7. 树状数组的 addDiff(r+1, -v) 在 r = n 时越界。 用 for (i = x; i <= n; ...) 的写法自然规避，但如果你手动访问 tree[r+1] 就会出事。
  8. 递归里忘记不相交判断。 建议在递归函数开头写上 if (R < l || r < L) return;，比 if (L <= mid) 这种分发写法更不容易漏。
  9. 离线离散化后忘了重建数据结构。 离散化改变的是整个坐标体系，必须重建。
  10. 在线题强行用离线思路。 带强制在线（^ last_ans）的题目不能排序询问、不能离散化，只能上线段树。

常见误区

误区一：”线段树万能，树状数组太简单没前途。”
恰恰相反，树状数组在大量题目里都是更优解，因为省内存、省常数。NOI 级别题目里”用线段树 TLE，换树状数组 AC”的案例非常多见。

误区二：”树状数组只能做前缀和。”
加上差分，它可以做区间和、区间加、甚至二维树状数组（单点改 + 矩形和）。但它做不了”区间 + 区间”以外的组合——这是它的边界。

误区三：”懒标记很难理解，绕开它只用树状数组。”
理解懒标记的最好方式是记住那个不变量：访问任何结点前，它的所有祖先标记必须已经下传。所以 pushdown 只在”部分相交”时调用，完全命中直接返回——这条规则本身就把懒标记的理解难度降下来了。

一句话总结：先用差分思维把问题翻译成”单点改 + 前缀查”，能翻译就用树状数组（快 2～4 倍、省 4 倍内存）；翻译不了（最值、复杂合并、在线）才用线段树。