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

代码模板

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

一句话算法

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

问题模型

给定长度为 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. 等以后查询或修改需要进入孩子时,再把这个标记传下去。

这个标记就叫懒标记。

懒标记表示什么

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

  • tag[p]:当前节点是否有尚未下传的赋值标记;
  • lazy[p]:如果有标记,这个区间要被赋成什么值。

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

cpp
        
1
2
3
tr[p] = x * (r - l + 1); // 区间和直接按长度算出来 lazy[p] = x; tag[p] = true;

注意:区间赋值不是区间加法。新的赋值会覆盖旧的赋值标记;加法标记则是会累加的(见后面的区间加模板)。

算法步骤

区间赋值

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

区间查询

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

算法证明

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

当一个节点被完整覆盖时,直接设置 tr[p] = value * (r - l + 1),当前节点答案正确;记录懒标记表示孩子以后需要同步。

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

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

复杂度分析

设数组长度为 nn。

  • 建树:O(n)O(n)。
  • 区间赋值:O(log⁡n)O(\log n)。
  • 区间查询:O(log⁡n)O(\log n)。
  • 空间复杂度:O(n)O(n)。

代码实现

两份模板都用全局数组 + 自由函数,不使用 struct 或 class,节点与区间均为 1 下标。

接口 区间赋值模板 区间加模板
建树 seg_build(1, 1, n) seg_build(1, 1, n)
区间修改 assign_range(l, r, x, 1, 1, n) range_add(l, r, x, 1, 1, n)
区间查询 range_sum(l, r, 1, 1, n) range_sum(l, r, 1, 1, n)
懒标记 lazy[p] + tag[p](赋值会覆盖旧标记) lazy[p](加法会累加)
取模 不取模,用 long long mod 与 norm(),和与增量均取模

区间赋值模板更贴近“覆盖”语义(染色、赋值),区间加模板与树链剖分里的 sgt 段完全一致,可以直接整段搬到 HLD。

先看区间赋值版。模板输入格式:

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

其中:

  • op = 1 l r x 表示把 [l,r] 全部赋值为 x;
  • op = 2 l r 表示查询 [l,r] 的区间和。
C++
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
#include <bits/stdc++.h> using namespace std; using ll = long long; // 区间赋值 + 区间求和线段树(懒标记),节点与区间均为 1 下标。 const int maxn = 100000 + 5; // 按题目规模调整,n 不能超过 maxn ll base[maxn]; // 原始数组,建树时用 base[1..n] ll tr[maxn << 2]; // tr[p]:节点 p 管辖区间的和 ll lazy[maxn << 2]; // lazy[p]:待下传的赋值值 bool tag[maxn << 2]; // tag[p]:p 是否挂着未下传的赋值标记 int ls(int p) { return p << 1; } // p 的左儿子 2p int rs(int p) { return p << 1 | 1; } // p 的右儿子 2p+1 // 把节点 p 的整个区间 [l, r] 赋值为 value:区间和 = value * 长度 void apply(int p, int l, int r, ll value) { tr[p] = value * (r - l + 1); lazy[p] = value; tag[p] = true; } // 下推:把 p 的赋值标记传给两个孩子 void pushdown(int p, int l, int r) { // 没有标记无事可做;叶子没有儿子可下放,必须提前返回 if (!tag[p] || l == r) return; int mid = (l + r) >> 1; apply(ls(p), l, mid, lazy[p]); apply(rs(p), mid + 1, r, lazy[p]); tag[p] = false; // 标记已经下放,清掉 } // 用 base[1..n] 建树 void seg_build(int p, int l, int r) { tag[p] = false; // 建树时顺手清标记,换数据不必整体清零 if (l == r) { tr[p] = base[l]; return; } int mid = (l + r) >> 1; seg_build(ls(p), l, mid); seg_build(rs(p), mid + 1, r); tr[p] = tr[ls(p)] + tr[rs(p)]; } // 区间赋值:把 [ql, qr] 全部赋值为 value void assign_range(int ql, int qr, ll value, int p, int l, int r) { if (qr < l || r < ql) return; if (ql <= l && r <= qr) { apply(p, l, r, value); return; } pushdown(p, l, r); // 要进入孩子,先把标记下放 int mid = (l + r) >> 1; assign_range(ql, qr, value, ls(p), l, mid); assign_range(ql, qr, value, rs(p), mid + 1, r); tr[p] = tr[ls(p)] + tr[rs(p)]; } // 区间和:把 [ql, qr] 拆成不交的若干节点,逐个累加 ll range_sum(int ql, int qr, int p, int l, int r) { if (qr < l || r < ql) return 0; if (ql <= l && r <= qr) return tr[p]; pushdown(p, l, r); // 孩子的值可能还没跟上父节点的标记 int mid = (l + r) >> 1; ll answer = range_sum(ql, qr, ls(p), l, mid); answer += range_sum(ql, qr, rs(p), mid + 1, r); return answer; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; for (int i = 1; i <= n; i++) cin >> base[i]; seg_build(1, 1, n); while (m--) { int op; cin >> op; if (op == 1) { int l, r; ll x; cin >> l >> r >> x; assign_range(l, r, x, 1, 1, n); } else { int l, r; cin >> l >> r; cout << range_sum(l, r, 1, 1, n) << '\n'; } } return 0; }
Python
python
        
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
# 区间赋值 + 区间求和线段树(懒标记),节点与区间均为 1 下标。 # 与 C++ 版一一对应:全局列表 base / tr / lazy / tag,配 init(n) 与独立函数。 # 懒标记不变量:tag[p] 为真时,p 的整个区间被统一赋为 lazy[p],但两个孩子的 tr # 还没跟上;pushdown 把标记下放到孩子并清空。段内关系 tr[p] = lazy[p] * 区间长度。 # 递归深度是线段树高度 O(log n),不会触及默认递归上限。 base: list[int] = [] # 原始数组,建树时用 base[1..n] tr: list[int] = [] # tr[p]:节点 p 管辖区间的和 lazy: list[int] = [] # lazy[p]:待下传的赋值值 tag: list[bool] = [] # tag[p]:p 是否挂着未下传的赋值标记 n: int = 0 # 数组长度 def init(size: int) -> None: """重置为区间 [1, size];换一组数据前必须先调用。""" global n, base, tr, lazy, tag n = size base = [0] * (n + 1) tr = [0] * (n * 4 + 5) lazy = [0] * (n * 4 + 5) tag = [False] * (n * 4 + 5) def ls(p: int) -> int: return p << 1 # 左儿子 2p def rs(p: int) -> int: return p << 1 | 1 # 右儿子 2p+1 def apply(p: int, l: int, r: int, value: int) -> None: """把节点 p 的整个区间 [l, r] 赋值为 value。""" tr[p] = value * (r - l + 1) lazy[p] = value tag[p] = True def pushdown(p: int, l: int, r: int) -> None: """下推赋值标记;叶子没有孩子可下放,必须提前返回。""" if not tag[p] or l == r: return mid = (l + r) >> 1 apply(ls(p), l, mid, lazy[p]) apply(rs(p), mid + 1, r, lazy[p]) tag[p] = False # 标记已经下放,清掉 def seg_build(p: int, l: int, r: int) -> None: """用 base[1..n] 建树。""" tag[p] = False # 建树时顺手清标记,换数据不必整体清零 if l == r: tr[p] = base[l] return mid = (l + r) >> 1 seg_build(ls(p), l, mid) seg_build(rs(p), mid + 1, r) tr[p] = tr[ls(p)] + tr[rs(p)] def assign_range(ql: int, qr: int, value: int, p: int, l: int, r: int) -> None: """把 [ql, qr] 全部赋值为 value。""" if qr < l or r < ql: return if ql <= l and r <= qr: apply(p, l, r, value) return pushdown(p, l, r) # 要进入孩子,先把标记下放 mid = (l + r) >> 1 assign_range(ql, qr, value, ls(p), l, mid) assign_range(ql, qr, value, rs(p), mid + 1, r) tr[p] = tr[ls(p)] + tr[rs(p)] def range_sum(ql: int, qr: int, p: int, l: int, r: int) -> int: """返回 [ql, qr] 的区间和。""" if qr < l or r < ql: return 0 if ql <= l and r <= qr: return tr[p] pushdown(p, l, r) # 孩子的值可能还没跟上父节点的标记 mid = (l + r) >> 1 answer = range_sum(ql, qr, ls(p), l, mid) answer += range_sum(ql, qr, rs(p), mid + 1, r) return answer

换成加法标记

区间加模板的输入输出与上面一致,只把 op = 1 l r x 的含义改成“把 [l,r] 每个数都加上 x”。改动集中在三处:

  • apply:tr[p] = (tr[p] + value * len) % mod,lazy[p] = (lazy[p] + value) % mod(赋值是覆盖,加法是累加);
  • pushdown:判据从 tag[p] 换成 lazy[p] != 0,下推后 lazy[p] = 0;
  • 建树与上推:每个加法都套一层 % mod,建树时叶子要 norm(base[l]) 把负初值归一。
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
#include <bits/stdc++.h> using namespace std; using ll = long long; // 懒标记线段树(区间加 + 区间和,取模),节点与区间均为 1 下标。 // 这段 sgt 与 HLD 模板里的 sgt 段完全一致,可以整段搬到树链剖分里用。 const int maxn = 100000 + 5; // 按题目规模调整,n 不能超过 maxn int mod = 1000000007; // 取模的模数,做题时按题面赋值 ll base[maxn]; // 原始数组,建树时用 base[1..n] ll tr[maxn << 2]; // tr[p]:节点 p 管辖区间的和 ll lazy[maxn << 2]; // lazy[p]:待下传给儿子的加法标记 // 把可能为负的 x 归一到 [0, mod):只用在“外来值”上(输入的初值和增量)。 ll norm(ll x) { return (x % mod + mod) % mod; } int ls(int p) { return p << 1; } // p 的左儿子 2p int rs(int p) { return p << 1 | 1; } // p 的右儿子 2p+1 // 把节点 p 的整个区间 [l, r] 整体加 value:区间和加上 value * 长度 void apply(int p, int l, int r, ll value) { value = norm(value); tr[p] = (tr[p] + value * (r - l + 1)) % mod; lazy[p] = (lazy[p] + value) % mod; } void pushdown(int p, int l, int r) { // 懒标记为 0 无事可做;叶子没有儿子可下放,必须提前返回, // 否则 mid = l,会递归进入自己并且写越界的 tr[2p]。 if (!lazy[p] || l == r) return; int mid = (l + r) >> 1; apply(ls(p), l, mid, lazy[p]); apply(rs(p), mid + 1, r, lazy[p]); lazy[p] = 0; } // 用 base[1..n] 建树 void seg_build(int p, int l, int r) { lazy[p] = 0; // 建树时顺手清懒标记,换数据不必整体清零 if (l == r) { tr[p] = norm(base[l]); return; } int mid = (l + r) >> 1; seg_build(ls(p), l, mid); seg_build(rs(p), mid + 1, r); tr[p] = (tr[ls(p)] + tr[rs(p)]) % mod; } // 区间加:把 [ql, qr] 整体加 value。 void range_add(int ql, int qr, ll value, int p, int l, int r) { if (qr < l || r < ql) return; if (ql <= l && r <= qr) { apply(p, l, r, value); return; } pushdown(p, l, r); int mid = (l + r) >> 1; range_add(ql, qr, value, ls(p), l, mid); range_add(ql, qr, value, rs(p), mid + 1, r); tr[p] = (tr[ls(p)] + tr[rs(p)]) % mod; } // 区间和:把 [ql, qr] 拆成不交的若干节点,逐个累加。 ll range_sum(int ql, int qr, int p, int l, int r) { if (qr < l || r < ql) return 0; if (ql <= l && r <= qr) return tr[p]; pushdown(p, l, r); int mid = (l + r) >> 1; ll answer = range_sum(ql, qr, ls(p), l, mid); answer += range_sum(ql, qr, rs(p), mid + 1, r); return answer % mod; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; for (int i = 1; i <= n; i++) cin >> base[i]; seg_build(1, 1, n); while (m--) { int op; cin >> op; if (op == 1) { int l, r; ll x; cin >> l >> r >> x; range_add(l, r, x, 1, 1, n); } else { int l, r; cin >> l >> r; cout << range_sum(l, r, 1, 1, n) << '\n'; } } return 0; }

Python 版 init(n, mod) 多一个模数参数,apply / seg_build / range_sum 里的取模与 C++ 一一对应。

python
        
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
# 懒标记线段树(区间加 + 区间和,取模),节点与区间均为 1 下标。 # 与 C++ 版、HLD 模板里的 sgt 段一一对应:全局列表 base / tr / lazy + init(n)。 # 懒标记不变量:lazy[p] 表示“p 的整个区间还要给每个孩子各加这么多”, # 但不影响 p 自己(p 的 tr 已经加过了);pushdown 后清成 0。 # 递归深度是线段树高度 O(log n),不会触及默认递归上限。 # Python int 任意精度,不必像 C++ 那样担心 value * 长度 溢出。 base: list[int] = [] # 原始数组,建树时用 base[1..n] tr: list[int] = [] # tr[p]:节点 p 管辖区间的和(已取模) lazy: list[int] = [] # lazy[p]:待下传到两个孩子的加法标记 n: int = 0 # 数组长度 mod: int = 1000000007 # 取模的模数,做题时按题面赋值 def init(size: int, modulus: int) -> None: """重置为区间 [1, size] 与模数 modulus;换一组数据前必须先调用。""" global n, mod, base, tr, lazy n = size mod = modulus base = [0] * (n + 1) tr = [0] * (n * 4 + 5) lazy = [0] * (n * 4 + 5) def ls(p: int) -> int: return p << 1 # 左儿子 2p def rs(p: int) -> int: return p << 1 | 1 # 右儿子 2p+1 def norm(x: int) -> int: """把可能为负的 x 归一到 [0, mod)。""" return x % mod def apply(p: int, l: int, r: int, value: int) -> None: """把节点 p 的整个区间 [l, r] 整体加 value。""" value = norm(value) tr[p] = (tr[p] + value * (r - l + 1)) % mod lazy[p] = (lazy[p] + value) % mod def pushdown(p: int, l: int, r: int) -> None: """下推加法标记;叶子没有孩子可下放,必须提前返回。""" if lazy[p] == 0 or l == r: return mid = (l + r) >> 1 apply(ls(p), l, mid, lazy[p]) apply(rs(p), mid + 1, r, lazy[p]) lazy[p] = 0 def seg_build(p: int, l: int, r: int) -> None: """用 base[1..n] 建树。""" lazy[p] = 0 # 建树时顺手清懒标记,换数据不必整体清零 if l == r: tr[p] = norm(base[l]) return mid = (l + r) >> 1 seg_build(ls(p), l, mid) seg_build(rs(p), mid + 1, r) tr[p] = (tr[ls(p)] + tr[rs(p)]) % mod def range_add(ql: int, qr: int, value: int, p: int, l: int, r: int) -> None: """把 [ql, qr] 整体加 value。""" if qr < l or r < ql: return if ql <= l and r <= qr: apply(p, l, r, value) return pushdown(p, l, r) mid = (l + r) >> 1 range_add(ql, qr, value, ls(p), l, mid) range_add(ql, qr, value, rs(p), mid + 1, r) tr[p] = (tr[ls(p)] + tr[rs(p)]) % mod def range_sum(ql: int, qr: int, p: int, l: int, r: int) -> int: """返回 [ql, qr] 的区间和(已取模)。""" if qr < l or r < ql: return 0 if ql <= l and r <= qr: return tr[p] pushdown(p, l, r) mid = (l + r) >> 1 answer = range_sum(ql, qr, ls(p), l, mid) answer += range_sum(ql, qr, rs(p), mid + 1, r) return answer % mod

测试用例

输入:

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

这组数据没有负数,也不会触碰取模,所以区间赋值与区间加两个模板得到相同的 3 个数。区间加模板自己的取模与负增量行为需要单独验,直接拿模板文件(默认 mod 取 1000000007)跑下面这组:

3 5
-5 0 7
2 1 3
1 1 2 -3
2 1 2
2 1 3
1 2 2 100

输出为:

2
999999996
1000000003

初始和是 -5 + 0 + 7 = 2;1 1 2 -3 让前两个位置各减 3,此时区间 [1,2] 的真实和是 -11,取模后输出 999999996;整段和变成 -4,取模后输出 1000000003。最后一条命令只做修改、不输出,用来验证取模后后续操作仍然正确。

应用分类详解

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

一、区间赋值,区间求和

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

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

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

二、区间加法,区间求和

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

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

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

三、区间染色与覆盖统计

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

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

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

经典例题

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

练习懒标记的 apply、pushdown、seg_build 三个核心函数。

2. 区间染色问题

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

3. 区间加法求和题

直接用前一节的区间加模板,它把赋值标记换成了累加的加法标记,是更常见的区间加区间和写法。

参考

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