动态开点线段树

代码模板

解决值域过大无法建立完整线段树时的内存分配问题,通过按需创建节点节省空间。

一句话算法

线段树的节点只有在用到的时候才被创建出来(懒惰创建,按需分配)。

问题模型

给定一个值域区间非常大(例如 1⩽x⩽1091 \leqslant x \leqslant 10^9 甚至更大)的初始全为 00 的数组。我们需要支持:

  1. 单点修改/区间修改:在坐标 xx 处加上 vv。
  2. 区间查询:查询 [l,r][l, r] 上的总和/最值等。

常规线段树需要开 4×1094 \times 10^9 的空间,这在一般竞赛的 256MB256 \text{MB} 或 512MB512 \text{MB} 内存限制下会直接导致 Memory Limit Exceeded (MLE)。但是,如果修改操作的总次数 mm 相对较小(例如 m⩽105m \leqslant 10^5),这意味着绝大部分数组元素仍然是初始值 00。

核心直觉

普通线段树是静态建树:一开始就把代表所有区间的节点全部建好。

动态开点线段树(Dynamic Segment Tree,有时又叫 Implicit Segment Tree)的核心在于按需分配(Lazy Allocation):一开始整棵树只有一个根节点,当我们需要修改或访问某个区间时,如果代表这个区间的子节点不存在,我们才去创建它。那些从未被访问到的区间,连节点都不会生成,这就极大地节省了内存。

由于节点的分配是随机的,我们不能再用乘 2 的方式寻找儿子(即 2p2p 和 2p+12p+1 不再适用),而是需要像写平衡树那样,在每个节点里专门用两个变量 ls[p] 和 rs[p] 来记录它的左儿子和右儿子的编号。

算法步骤

  1. 节点分配:维护一个全局计数器 tot。每次需要新节点时,++tot,并返回这个新的编号。
  2. 修改过程:从根节点开始递归。在经过某个节点 p 时,如果 p 为 00(空),那么就给它分配一个编号 p = ++tot。然后再看修改的位置落在左半边还是右半边,决定往左还是往右递归更新。最后在回溯时,利用左右儿子的信息更新当前节点的值 sum[p]。
  3. 查询过程:从根节点向下递归查询。如果遇到某个节点 p 为 00,说明这个节点及它下属的区间都未被修改过,可以直接返回初始值 00,此时坚决不需要创建该节点。

复杂度分析

  • 时间复杂度:不管是修改还是查询,每次递归深入一层,区间长度减半。线段树的高度为 log⁡V\log V(VV 是值域大小),因此单次操作的时间复杂度为 O(log⁡V)O(\log V)。
  • 空间复杂度:由于只在修改时才创建节点,每次单点修改会沿着树根走到叶子,最多经过 log⁡V\log V 个节点。如果有 mm 次修改操作,那么最多会创建 mlog⁡Vm \log V 个节点。所以空间复杂度为 O(mlog⁡V)O(m \log V)。对于 m=105,V=109m = 10^5, V = 10^9 的情况,mlog⁡2V≈3×106m \log_2 V \approx 3 \times 10^6,空间是完全可以承受的。

代码模板

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
#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; }
Python

C++ 用 int& 引用出参回写根,Python 版 update 返回新根,调用方须写 root = update(root, ...)。两个版本都是全局数组加自由函数,init() 负责清空节点池。

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
# 动态开点线段树:值域可以很大(如 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

数组大小怎么开

通常在考试中,如果总操作次数为 mm,值域大小上限是 VV,那么最坏情况下会开辟 m⌈log⁡2V⌉m \lceil \log_2 V \rceil 个节点。为了安全起见,通常还会加上常数项,例如开 mlog⁡2V+100m \log_2 V + 100 大小。只要不超过内存限制,数组可以尽量开大一些。

代码实现

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
#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; }
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
# 动态开点线段树示例,对应同目录 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 包含了一个极端的测试,在值域高达 10910^9 的数组中对三个坐标 10001000、2×1062 \times 10^6 和 999999999999999999 分别加上 5,10,205, 10, 20。

  • 区间 [1,10000][1, 10000] 只有 10001000 这一个修改点,所以查询和应为 55。
  • 区间 [1,109][1, 10^9] 包含了所有的修改,和应为 5+10+20=355 + 10 + 20 = 35。
  • tree.tot 将输出几十左右,这意味着在 10910^9 的巨大值域下,仅分配几十个节点就完成了数据维护,完美避开了 4×1094 \times 10^9 的 MLE 风险。

应用分类详解

动态开点线段树通过节约内存,使得线段树能够被更灵活地嵌套和使用。

一、 强制在线的值域操作问题

典型模式: 在一根坐标从 −109-10^9 到 10910^9 的数轴上进行单点或区间操作,且强制在线。 识别信号: 值域大,无法开出 O(V)O(V) 的数组。如果题目允许离线,我们通常首选离散化,因为好写且常数小;但如果强制在线无法离散化,就必须用动态开点线段树。 核心建模: 直接把操作区间看作 [1,V][1, V],套用动态开点模板。

二、 作为高级数据结构的底层组件(树套树)

典型模式: 二维线段树(线段树套线段树)、线段树套平衡树等。 识别信号: 处理二维平面信息、带修区间第 k 小。 核心建模: 在外层线段树的每一个节点上,再挂一棵内层线段树。由于外层树有 O(n)O(n) 个节点,如果每个内层树都建满,空间会爆炸。所以内层树通常采用动态开点的方式构建。

三、 线段树合并与分裂的基础

典型模式: 每个树节点上有一棵自己的权值线段树,需要把儿子节点的信息合并给父亲。 识别信号: 树上问题 + 维护集合的值域信息(如某个权值出现的次数)。 核心建模: 必须使用动态开点权值线段树。在合并两棵树时,对应节点如果有空就直接指针复用,极大地提高了效率并降低了空间。可以说,没有动态开点,就无法实现线段树合并和可持久化线段树(主席树)。

经典例题

  • 洛谷 P13825 线段树 1.5【动态开点线段树】
    • 核心思路:最标准的动态开点练习题,值域变大,照抄模板即可。
  • 二维偏序/逆序对在线求解
    • 核心思路:虽然常用树状数组,但在某些强制在线的值域更新题里,动态开点权值线段树同样是非常直接的解法。
  • 扫描线的不离散化写法
    • 核心思路:扫描线求面积交如果不想手写离散化,可以直接把坐标映射在 10910^9 范围内,上线段树的动态开点区间修改(注意区间修改需要 pushdown 时动态开点下放标记)。