动态开点线段树
代码模板解决值域过大无法建立完整线段树时的内存分配问题,通过按需创建节点节省空间。
一句话算法
线段树的节点只有在用到的时候才被创建出来(懒惰创建,按需分配)。
问题模型
给定一个值域区间非常大(例如
- 单点修改/区间修改:在坐标
处加上 。 - 区间查询:查询
上的总和/最值等。
常规线段树需要开
核心直觉
普通线段树是静态建树:一开始就把代表所有区间的节点全部建好。
动态开点线段树(Dynamic Segment Tree,有时又叫 Implicit Segment Tree)的核心在于按需分配(Lazy Allocation):一开始整棵树只有一个根节点,当我们需要修改或访问某个区间时,如果代表这个区间的子节点不存在,我们才去创建它。那些从未被访问到的区间,连节点都不会生成,这就极大地节省了内存。
由于节点的分配是随机的,我们不能再用乘 2 的方式寻找儿子(即 ls[p] 和 rs[p] 来记录它的左儿子和右儿子的编号。
算法步骤
- 节点分配:维护一个全局计数器
tot。每次需要新节点时,++tot,并返回这个新的编号。 - 修改过程:从根节点开始递归。在经过某个节点
p时,如果p为(空),那么就给它分配一个编号 p = ++tot。然后再看修改的位置落在左半边还是右半边,决定往左还是往右递归更新。最后在回溯时,利用左右儿子的信息更新当前节点的值sum[p]。 - 查询过程:从根节点向下递归查询。如果遇到某个节点
p为,说明这个节点及它下属的区间都未被修改过,可以直接返回初始值 ,此时坚决不需要创建该节点。
复杂度分析
- 时间复杂度:不管是修改还是查询,每次递归深入一层,区间长度减半。线段树的高度为
( 是值域大小),因此单次操作的时间复杂度为 。 - 空间复杂度:由于只在修改时才创建节点,每次单点修改会沿着树根走到叶子,最多经过
个节点。如果有 次修改操作,那么最多会创建 个节点。所以空间复杂度为 。对于 的情况, ,空间是完全可以承受的。
代码模板
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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// 动态开点线段树:值域可以很大(如 1e9),只在真正访问到的位置分配节点。
// 空间 O(m log V):m 次修改,每次最多新增 log V 个节点。
// 与普通线段树相比,这类题的数组没法按值域直接开,只能靠节点池。
const int MAXNODE = 3000005; // 节点池:按 m log V 估,再留一点余量
int lc[MAXNODE]; // lc[p]:p 的左儿子下标,0 表示空
int rc[MAXNODE]; // rc[p]:p 的右儿子下标,0 表示空
ll sum[MAXNODE]; // sum[p]:p 管辖区间内所有数之和
int root = 0; // 根节点下标,0 表示空树
int tot = 0; // 已分配的节点数,0 号节点固定为空节点
// 新建一个空节点并返回它的下标
int new_node() {
++tot;
lc[tot] = rc[tot] = 0;
sum[tot] = 0;
return tot;
}
// 单点加:在值域区间 [l, r] 上把 x 位置加上 value。
// p 用引用传参,节点为空时在这里分配,新编号会直接写回父节点的孩子。
void update(int &p, ll l, ll r, ll x, ll value) {
if (!p) p = new_node(); // 走到空节点就开一个,这是“动态开点”
if (l == r) {
sum[p] += value;
return;
}
ll mid = l + ((r - l) >> 1); // 防溢出的中点写法
if (x <= mid) update(lc[p], l, mid, x, value);
else update(rc[p], mid + 1, r, x, value);
sum[p] = sum[lc[p]] + sum[rc[p]];
}
// 区间和:节点为空说明整段都是 0,直接返回,绝不在这里开点
ll query(int p, ll l, ll r, ll ql, ll qr) {
if (!p || qr < l || r < ql) return 0;
if (ql <= l && r <= qr) return sum[p];
ll mid = l + ((r - l) >> 1);
ll answer = query(lc[p], l, mid, ql, qr);
answer += query(rc[p], mid + 1, r, ql, qr);
return answer;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
// 例题:值域 [1, 1e9] 上的单点加与区间求和
ll limit = 1000000000;
update(root, 1, limit, 1000, 5); // 在位置 1000 加上 5
update(root, 1, limit, 2000000, 10); // 在位置 2000000 加上 10
update(root, 1, limit, 999999999, 20); // 在位置 999999999 加上 20
// [1, 10000] 只包含位置 1000,所以答案是 5
cout << query(root, 1, limit, 1, 10000) << '\n';
// 整个值域包含全部修改,所以答案是 5 + 10 + 20 = 35
cout << query(root, 1, limit, 1, limit) << '\n';
// 在 1e9 的值域上只用了这么点节点,正好说明动态开点省空间
cout << "Allocated nodes: " << tot << '\n';
return 0;
}
C++ 用 int& 引用出参回写根,Python 版 update 返回新根,调用方须写 root = update(root, ...)。两个版本都是全局数组加自由函数,init() 负责清空节点池。
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
# 动态开点线段树:值域可以很大(如 1e9),只在真正访问到的位置分配节点。
# 空间 O(m log V):m 次修改,每次最多新增 log V 个节点。
# 与 C++ 版一一对应:全局列表 lc / rc / sum(下标即指针)+ 独立函数。
# C++ 用 int& 引用出参回写根,Python 没有引用传参,update 改为返回新根,
# 调用方须写 root = update(root, ...)。
# 递归深度 O(log(值域)),1e18 也只有约 60 层,安全。
lc: list[int] = [0] # lc[p]:p 的左儿子下标,0 表示空
rc: list[int] = [0] # rc[p]:p 的右儿子下标,0 表示空
sum_: list[int] = [0] # sum_[p]:p 管辖区间内所有数之和
root: int = 0 # 根节点下标,0 表示空树
tot: int = 0 # 已分配的节点数,0 号节点固定为空节点
def init() -> None:
"""清空整棵树,换一组数据前必须先调用。"""
global lc, rc, sum_, root, tot
lc = [0]
rc = [0]
sum_ = [0]
root = 0
tot = 0
def new_node() -> int:
"""新建一个空节点并返回它的下标。"""
global tot
tot += 1
lc.append(0)
rc.append(0)
sum_.append(0)
return tot
def update(p: int, l: int, r: int, x: int, value: int) -> int:
"""单点加:在值域区间 [l, r] 上把 x 位置加 value,返回该子树的根。"""
if p == 0:
p = new_node() # 走到空节点就开一个,这是“动态开点”
if l == r:
sum_[p] += value
return p
mid = l + ((r - l) >> 1) # 防溢出的中点写法
if x <= mid:
lc[p] = update(lc[p], l, mid, x, value)
else:
rc[p] = update(rc[p], mid + 1, r, x, value)
sum_[p] = sum_[lc[p]] + sum_[rc[p]]
return p
def query(p: int, l: int, r: int, ql: int, qr: int) -> int:
"""区间和:节点为空说明整段都是 0,直接返回,绝不在查询里开点。"""
if p == 0 or qr < l or r < ql:
return 0
if ql <= l and r <= qr:
return sum_[p]
mid = l + ((r - l) >> 1)
answer = query(lc[p], l, mid, ql, qr)
answer += query(rc[p], mid + 1, r, ql, qr)
return answer
数组大小怎么开
通常在考试中,如果总操作次数为
代码实现
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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// 动态开点线段树:值域可以很大(如 1e9),只在真正访问到的位置分配节点。
// 空间 O(m log V):m 次修改,每次最多新增 log V 个节点。
const int MAXNODE = 3000005; // 节点池:按 m log V 估,再留一点余量
int lc[MAXNODE]; // lc[p]:p 的左儿子下标,0 表示空
int rc[MAXNODE]; // rc[p]:p 的右儿子下标,0 表示空
ll sum[MAXNODE]; // sum[p]:p 管辖区间内所有数之和
int root = 0; // 根节点下标,0 表示空树
int tot = 0; // 已分配的节点数,0 号节点固定为空节点
// 新建一个空节点并返回它的下标
int new_node() {
++tot;
lc[tot] = rc[tot] = 0;
sum[tot] = 0;
return tot;
}
// 单点加:在值域区间 [l, r] 上把 x 位置加上 value。
// p 用引用传参,节点为空时在这里分配,新编号会直接写回父节点的孩子。
void update(int &p, ll l, ll r, ll x, ll value) {
if (!p) p = new_node(); // 走到空节点就开一个,这是“动态开点”
if (l == r) {
sum[p] += value;
return;
}
ll mid = l + ((r - l) >> 1); // 防溢出的中点写法
if (x <= mid) update(lc[p], l, mid, x, value);
else update(rc[p], mid + 1, r, x, value);
sum[p] = sum[lc[p]] + sum[rc[p]];
}
// 区间和:节点为空说明整段都是 0,直接返回,绝不在这里开点
ll query(int p, ll l, ll r, ll ql, ll qr) {
if (!p || qr < l || r < ql) return 0;
if (ql <= l && r <= qr) return sum[p];
ll mid = l + ((r - l) >> 1);
ll answer = query(lc[p], l, mid, ql, qr);
answer += query(rc[p], mid + 1, r, ql, qr);
return answer;
}
int main() {
// 例题:维护值域 [1, 10^9] 的单点修改、区间求和
ll limit = 1000000000;
update(root, 1, limit, 1000, 5); // 在位置 1000 加上 5
update(root, 1, limit, 2000000, 10); // 在位置 2000000 加上 10
update(root, 1, limit, 999999999, 20); // 在位置 999999999 加上 20
// 查询 [1, 10000] 的和,只包含位置 1000 的 5
cout << query(root, 1, limit, 1, 10000) << "\n";
// 查询 [1, 10^9] 的和,包含所有修改,应为 35
cout << query(root, 1, limit, 1, limit) << "\n";
// 输出共开辟的节点数,说明空间的高效利用
cout << "Allocated nodes: " << tot << "\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
# 动态开点线段树示例,对应同目录 example.cpp。
# 程序不读输入:在值域 [1, 1e9] 上做三次单点加,再查询两个区间。
# 与 example.cpp 一一对应:全局列表 lc / rc / sum_(下标即指针)+ 独立函数。
# 下标 0 表示空节点,节点从 1 开始编号;递归深度 O(log V) ≈ 30,安全。
import sys
lc: list[int] = [0] # lc[p]:p 的左儿子下标,0 表示空
rc: list[int] = [0] # rc[p]:p 的右儿子下标,0 表示空
sum_: list[int] = [0] # sum_[p]:p 管辖区间内所有数之和
root: int = 0 # 根节点下标,0 表示空树
tot: int = 0 # 已分配的节点数,0 号节点固定为空节点
def new_node() -> int:
"""新建一个空节点并返回它的下标。"""
global tot
tot += 1
lc.append(0)
rc.append(0)
sum_.append(0)
return tot
def update(p: int, l: int, r: int, x: int, value: int) -> int:
"""单点加:在值域 [l, r] 上把 x 位置加 value,返回该子树的根编号。
C++ 用 int& 出参直接改指针,Python 只能把新编号返回给调用方写回。
"""
if p == 0:
p = new_node() # 走到空节点就开一个,这是“动态开点”
if l == r:
sum_[p] += value
return p
mid = l + ((r - l) >> 1) # 防溢出的中点写法
if x <= mid:
lc[p] = update(lc[p], l, mid, x, value)
else:
rc[p] = update(rc[p], mid + 1, r, x, value)
sum_[p] = sum_[lc[p]] + sum_[rc[p]]
return p
def query(p: int, l: int, r: int, ql: int, qr: int) -> int:
"""区间和:没建过的子树贡献 0,查询里绝不开点。"""
if p == 0 or qr < l or r < ql:
return 0
if ql <= l and r <= qr:
return sum_[p]
mid = l + ((r - l) >> 1)
answer = query(lc[p], l, mid, ql, qr)
answer += query(rc[p], mid + 1, r, ql, qr)
return answer
def main() -> None:
global root
limit = 10**9
root = update(root, 1, limit, 1000, 5)
root = update(root, 1, limit, 2000000, 10)
root = update(root, 1, limit, 999999999, 20)
# [1, 10000] 只覆盖 1000 这个修改点。
sys.stdout.write(str(query(root, 1, limit, 1, 10000)) + "\n")
# [1, 1e9] 覆盖全部三个修改点。
sys.stdout.write(str(query(root, 1, limit, 1, limit)) + "\n")
sys.stdout.write(f"Allocated nodes: {tot}\n")
if __name__ == "__main__":
main()
测试用例
上述 example.cpp 包含了一个极端的测试,在值域高达
- 区间
只有 这一个修改点,所以查询和应为 。 - 区间
包含了所有的修改,和应为 。 tree.tot将输出几十左右,这意味着在的巨大值域下,仅分配几十个节点就完成了数据维护,完美避开了 的 MLE 风险。
应用分类详解
动态开点线段树通过节约内存,使得线段树能够被更灵活地嵌套和使用。
一、 强制在线的值域操作问题
典型模式: 在一根坐标从
二、 作为高级数据结构的底层组件(树套树)
典型模式: 二维线段树(线段树套线段树)、线段树套平衡树等。
识别信号: 处理二维平面信息、带修区间第 k 小。
核心建模: 在外层线段树的每一个节点上,再挂一棵内层线段树。由于外层树有
三、 线段树合并与分裂的基础
典型模式: 每个树节点上有一棵自己的权值线段树,需要把儿子节点的信息合并给父亲。 识别信号: 树上问题 + 维护集合的值域信息(如某个权值出现的次数)。 核心建模: 必须使用动态开点权值线段树。在合并两棵树时,对应节点如果有空就直接指针复用,极大地提高了效率并降低了空间。可以说,没有动态开点,就无法实现线段树合并和可持久化线段树(主席树)。
经典例题
- 洛谷 P13825 线段树 1.5【动态开点线段树】
- 核心思路:最标准的动态开点练习题,值域变大,照抄模板即可。
- 二维偏序/逆序对在线求解
- 核心思路:虽然常用树状数组,但在某些强制在线的值域更新题里,动态开点权值线段树同样是非常直接的解法。
- 扫描线的不离散化写法
- 核心思路:扫描线求面积交如果不想手写离散化,可以直接把坐标映射在
范围内,上线段树的动态开点区间修改(注意区间修改需要 pushdown 时动态开点下放标记)。
- 核心思路:扫描线求面积交如果不想手写离散化,可以直接把坐标映射在