线段树:区间赋值与区间查询
代码模板线段树区间赋值与区间查询的原理与实现:懒标记延迟下传。
一句话算法
区间修改线段树把整段修改先记在大区间节点上,等以后必须访问孩子时再把标记下传。
问题模型
给定长度为
- 区间赋值:把
a[l..r]全部改成x。 - 区间查询:求
a[l] + ... + a[r]。
如果区间赋值时逐个修改元素,一次操作最坏是
核心直觉
线段树查询时,如果一个节点区间完全被目标区间覆盖,可以直接使用这个节点的答案。
区间修改也一样:如果当前节点区间完全被修改区间覆盖,就没有必要继续递归到每个叶子。
我们只需要:
- 直接更新当前节点的区间和;
- 给当前节点打一个“整段已经被赋值为 x”的标记;
- 等以后查询或修改需要进入孩子时,再把这个标记传下去。
这个标记就叫懒标记。
懒标记表示什么
对区间赋值来说,懒标记需要记录两件事:
tag[p]:当前节点是否有尚未下传的赋值标记;lazy[p]:如果有标记,这个区间要被赋成什么值。
当节点 [l,r] 被整体赋值为 x 时:
1
2
3
tr[p] = x * (r - l + 1); // 区间和直接按长度算出来
lazy[p] = x;
tag[p] = true;
注意:区间赋值不是区间加法。新的赋值会覆盖旧的赋值标记;加法标记则是会累加的(见后面的区间加模板)。
算法步骤
区间赋值
- 当前节点区间为
[l,r]。 - 如果
[l,r]完全包含在[L,R]中:- 更新
tr[p]; - 记录懒标记
lazy[p]并置tag[p] = true; - 返回。
- 更新
- 否则先
pushdown(p),把旧标记下传给孩子。 - 递归修改与
[L,R]相交的孩子。 - 回溯时重新合并当前节点。
区间查询
- 如果当前节点区间完全在查询区间内,直接返回
tr[p]。 - 否则先
pushdown(p),保证孩子信息正确。 - 递归查询相交的孩子。
- 合并答案。
算法证明
核心不变量:tr[p] 始终表示节点 p 对应区间的真实区间和;若 tag[p] 为真,则它的孩子可能还没更新,但整个节点区间已经被统一赋值为 lazy[p]。
当一个节点被完整覆盖时,直接设置 tr[p] = value * (r - l + 1),当前节点答案正确;记录懒标记表示孩子以后需要同步。
当后续操作必须访问孩子时,pushdown 会把赋值标记应用到两个孩子,使孩子的 tr[p] 与 lazy[p] 都正确。然后继续递归,回溯时重新合并父节点。
因此每次操作结束后,不变量仍成立,查询得到的区间和正确。
复杂度分析
设数组长度为
- 建树:
。 - 区间赋值:
。 - 区间查询:
。 - 空间复杂度:
。
代码实现
两份模板都用全局数组 + 自由函数,不使用 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]的区间和。
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;
}
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])把负初值归一。
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++ 一一对应。
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