我的算法书 - 线段树：区间赋值与区间查询

一句话算法

区间修改线段树把整段修改先记在大区间节点上，等以后必须访问孩子时再把标记下传。

问题模型

给定长度为 $n$ 的数组，支持两类操作：

区间赋值：把 a[l..r] 全部改成 x。
区间查询：求 a[l] + ... + a[r]。

如果区间赋值时逐个修改元素，一次操作最坏是 $O(n)$ 。懒标记线段树可以把区间修改和区间查询都做到 $O(\log n)$ 。

核心直觉

线段树查询时，如果一个节点区间完全被目标区间覆盖，可以直接使用这个节点的答案。

区间修改也一样：如果当前节点区间完全被修改区间覆盖，就没有必要继续递归到每个叶子。

我们只需要：

直接更新当前节点的区间和；
给当前节点打一个“整段已经被赋值为 x”的标记；
等以后查询或修改需要进入孩子时，再把这个标记传下去。

这个标记就叫懒标记。

懒标记表示什么

对区间赋值来说，懒标记需要记录两件事：

has_lazy[p]：当前节点是否有尚未下传的赋值标记；
lazy[p]：如果有标记，这个区间要被赋成什么值。

当节点 [l,r] 被整体赋值为 x 时：

cpp

        1
2
3

        tree[p] = x * (r - l + 1);
lazy[p] = x;
has_lazy[p] = true;

注意：区间赋值不是区间加法。新的赋值会覆盖旧的赋值标记。

算法步骤

区间赋值

当前节点区间为 [l,r]。
如果 [l,r] 完全包含在 [L,R] 中：
- 更新 tree[p]；
- 记录懒标记；
- 返回。
否则先 push(p)，把旧标记下传给孩子。
递归修改与 [L,R] 相交的孩子。
回溯时重新合并当前节点。

区间查询

如果当前节点区间完全在查询区间内，直接返回 tree[p]。
否则先 push(p)，保证孩子信息正确。
递归查询相交的孩子。
合并答案。

算法证明

核心不变量：tree[p] 始终表示节点 p 对应区间的真实区间和；若 has_lazy[p] 为真，则它的孩子可能还没更新，但整个节点区间已经被统一赋值。

当一个节点被完整覆盖时，直接设置 tree[p]，当前节点答案正确；记录懒标记表示孩子以后需要同步。

当后续操作必须访问孩子时，push 会把赋值标记应用到两个孩子，使孩子的 tree 与 lazy 都正确。然后继续递归，回溯时 pull 重新合并父节点。

因此每次操作结束后，不变量仍成立，查询得到的区间和正确。

复杂度分析

设数组长度为 $n$ 。

建树： $O(n)$ 。
区间赋值： $O(\log n)$ 。
区间查询： $O(\log n)$ 。
空间复杂度： $O(n)$ 。

代码实现

模板输入格式：

n m
a1 a2 ... an
op ...

其中：

op = 1 l r x 表示把 [l,r] 全部赋值为 x；
op = 2 l r 表示查询 [l,r] 的区间和。

cpp

        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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108

        #include <bits/stdc++.h>
using namespace std;

template <typename T>
struct SegmentTreeRangeAssign {
    int n = 0;
    vector<T> tree;
    vector<T> lazy;
    vector<bool> has_lazy;

    SegmentTreeRangeAssign(int n = 0) {
        init(n);
    }

    void init(int size) {
        n = size;
        tree.assign(n * 4 + 5, 0);
        lazy.assign(n * 4 + 5, 0);
        has_lazy.assign(n * 4 + 5, false);
    }

    void pull(int p) {
        tree[p] = tree[p << 1] + tree[p << 1 | 1];
    }

    void apply(int p, int l, int r, T value) {
        tree[p] = value * (r - l + 1);
        lazy[p] = value;
        has_lazy[p] = true;
    }

    void push(int p, int l, int r) {
        if (!has_lazy[p] || l == r) return;

        int mid = (l + r) >> 1;
        apply(p << 1, l, mid, lazy[p]);
        apply(p << 1 | 1, mid + 1, r, lazy[p]);
        has_lazy[p] = false;
    }

    void build(const vector<T> &a, int l, int r, int p = 1) {
        if (l == r) {
            tree[p] = a[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(a, l, mid, p << 1);
        build(a, mid + 1, r, p << 1 | 1);
        pull(p);
    }

    void assign_range(int ql, int qr, T value, int l, int r, int p = 1) {
        if (ql <= l && r <= qr) {
            apply(p, l, r, value);
            return;
        }

        push(p, l, r);
        int mid = (l + r) >> 1;
        if (ql <= mid) assign_range(ql, qr, value, l, mid, p << 1);
        if (qr > mid) assign_range(ql, qr, value, mid + 1, r, p << 1 | 1);
        pull(p);
    }

    T query(int ql, int qr, int l, int r, int p = 1) {
        if (ql <= l && r <= qr) return tree[p];

        push(p, l, r);
        int mid = (l + r) >> 1;
        T answer = 0;
        if (ql <= mid) answer += query(ql, qr, l, mid, p << 1);
        if (qr > mid) answer += query(ql, qr, mid + 1, r, p << 1 | 1);
        return answer;
    }
};

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

    int n, m;
    cin >> n >> m;

    vector<long long> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    SegmentTreeRangeAssign<long long> seg(n);
    seg.build(a, 1, n);

    while (m--) {
        int op;
        cin >> op;
        if (op == 1) {
            int l, r;
            long long x;
            cin >> l >> r >> x;
            seg.assign_range(l, r, x, 1, n);
        } else {
            int l, r;
            cin >> l >> r;
            cout << seg.query(l, r, 1, n) << '\n';
        }
    }

    return 0;
}

测试用例

输入：

输出：

15
36
13

应用分类详解

区间修改线段树的本质是“整段操作先压缩记录，必要时再展开”。只要修改目标是一整段，且查询也是区间信息，就应该考虑懒标记。

一、区间赋值，区间求和

典型模式： 把一段全部改成同一个值，再查询区间和。

识别信号： 出现“区间覆盖”“区间染色”“整段改为 x”。

核心建模： 懒标记记录这段被赋成的值，节点和为 x * len。

二、区间加法，区间求和

典型模式： 给一段每个数都加上 x。

识别信号： 出现“区间加”“区间增加”“区间平移”。

核心建模： 懒标记记录待加值，节点和增加 x * len。

三、区间染色与覆盖统计

典型模式： 多次把区间染成某种颜色，最后统计颜色或覆盖长度。

识别信号： 出现“覆盖”“染色”“后来的操作覆盖前面的操作”。

核心建模： 区间赋值标记天然表示覆盖关系。

经典例题

1. 区间修改区间查询模板题

练习懒标记的 apply、push、pull 三个核心函数。

2. 区间染色问题

把颜色看作赋值标记。重点是理解新标记会覆盖旧标记。

3. 区间加法求和题

把赋值标记改成加法标记，可得到更常见的区间加区间和模板。

参考

本书单点修改线段树章节：data_structure/segment_tree/update_one/index.md