线段树：区间赋值与区间查询

线段树区间赋值与区间查询的原理与实现：懒标记延迟下传。

  • 数据结构
  • 线段树
  • 懒标记

一句话算法

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

问题模型

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

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

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

核心直觉

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

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

我们只需要：

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

这个标记就叫懒标记。

懒标记表示什么

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

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

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

cpp 
        
1
2
3

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

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

算法步骤

区间赋值

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

区间查询

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

算法证明

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

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

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

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

复杂度分析

设数组长度为 nn。

  • 建树：O(n)O(n)。
  • 区间赋值：O(log⁡n)O(\log n)。
  • 区间查询：O(log⁡n)O(\log n)。
  • 空间复杂度：O(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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130

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

// 区间赋值 + 区间求和线段树（懒标记）
struct SegmentTreeRangeAssign {
    // 线段树节点：value 为区间和，lazy 为待下传的赋值标记
    using T = long long;
    struct Node {
        T value = 0;    // 当前区间的真实区间和
        T lazy = 0;     // 待下传的赋值值
        bool has_lazy = false;  // 是否还有未下传的赋值标记

        // 合并两个孩子：区间和相加，合并结果不携带懒标记
        Node operator+(const Node &other) const {
            return Node{value + other.value, 0, false};
        }
    };

    // 左儿子 / 右儿子的节点编号
    static int lson(int p) { return p << 1; }
    static int rson(int p) { return p << 1 | 1; }

    // 区间 [l, r] 的中点
    static int mid(int l, int r) { return (l + r) >> 1; }

    int n = 0;              // 区间大小
    vector<Node> tree;      // 线段树数组

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

    void init(int size) {
        n = size;
        tree.assign(n * 4 + 5, Node{});
    }

    // 上推：用两个孩子合并出当前节点
    void push_up(int p) {
        tree[p] = tree[lson(p)] + tree[rson(p)];
    }

    // 把节点 p 的整个区间 [l, r] 赋值为 value
    void apply(int p, int l, int r, T value) {
        tree[p].value = value * (r - l + 1);
        tree[p].lazy = value;
        tree[p].has_lazy = true;
    }

    // 下推：把节点 p 的懒标记传给两个孩子
    void push_down(int p, int l, int r) {
        if (!tree[p].has_lazy || l == r) return;

        int m = mid(l, r);
        apply(lson(p), l, m, tree[p].lazy);
        apply(rson(p), m + 1, r, tree[p].lazy);
        tree[p].has_lazy = false;
    }

    // 用数组 a 建树
    void build(const vector<T> &a, int l, int r, int p = 1) {
        if (l == r) {
            tree[p].value = a[l];
            return;
        }
        int m = mid(l, r);
        build(a, l, m, lson(p));
        build(a, m + 1, r, rson(p));
        push_up(p);
    }

    // 区间赋值：把 [ql, qr] 全部赋值为 value
    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_down(p, l, r);
        int m = mid(l, r);
        if (ql <= m) assign_range(ql, qr, value, l, m, lson(p));
        if (qr > m) assign_range(ql, qr, value, m + 1, r, rson(p));
        push_up(p);
    }

    // 区间查询：[ql, qr] 的区间和
    T query(int ql, int qr, int l, int r, int p = 1) {
        if (ql <= l && r <= qr) return tree[p].value;

        push_down(p, l, r);
        int m = mid(l, r);
        T answer = 0;
        if (ql <= m) answer += query(ql, qr, l, m, lson(p));
        if (qr > m) answer += query(ql, qr, m + 1, r, rson(p));
        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 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;
}

测试用例

输入：

5 5
1 2 3 4 5
2 1 5
1 2 4 10
2 1 5
1 3 5 1
2 2 5

输出：

15
36
13

应用分类详解

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

一、区间赋值，区间求和

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

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

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

二、区间加法，区间求和

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

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

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

三、区间染色与覆盖统计

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

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

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

经典例题

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

练习懒标记的 apply、push_down、push_up 三个核心函数。

2. 区间染色问题

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

3. 区间加法求和题

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

参考

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