我的算法书 - 动态开点线段树

一句话算法

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

问题模型

给定一个值域区间非常大（例如 $1 \leqslant x \leqslant 10^9$ 甚至更大）的初始全为 $0$ 的数组。我们需要支持：

单点修改/区间修改：在坐标 $x$ 处加上 $v$ 。
区间查询：查询 $[l, r]$ 上的总和/最值等。

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

核心直觉

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

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

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

算法步骤

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

复杂度分析

时间复杂度：不管是修改还是查询，每次递归深入一层，区间长度减半。线段树的高度为 $\log V$ （ $V$ 是值域大小），因此单次操作的时间复杂度为 $O(\log V)$ 。
空间复杂度：由于只在修改时才创建节点，每次单点修改会沿着树根走到叶子，最多经过 $\log V$ 个节点。如果有 $m$ 次修改操作，那么最多会创建 $m \log V$ 个节点。所以空间复杂度为 $O(m \log V)$ 。对于 $m = 10^5, V = 10^9$ 的情况， $m \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

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

// 动态开点线段树 (Dynamic Segment Tree)
// 适用于值域很大（如 1e9），但实际访问节点较少的情况。
// 空间复杂度 O(M log V)，其中 M 为修改次数，V 为值域大小。
struct DynamicSegTree {
    static const int MAX_NODES = 3000005; // 根据 m log V 估算最大节点数
    int ls[MAX_NODES], rs[MAX_NODES]; // 左右儿子指针（数组下标模拟指针）
    long long sum[MAX_NODES]; // 节点维护的信息，如区间和
    int root = 0, tot = 0; // 根节点和节点分配器计数

    // 动态开点：引用传参，当节点为空时分配新节点
    void pushup(int p) {
        sum[p] = sum[ls[p]] + sum[rs[p]];
    }

    // 单点加
    void update(int &p, long long l, long long r, long long x, long long val) {
        if (!p) p = ++tot; // 如果节点不存在，则创建
        if (l == r) {
            sum[p] += val;
            return;
        }
        long long mid = l + ((r - l) >> 1); // 防止溢出
        if (x <= mid) update(ls[p], l, mid, x, val);
        else update(rs[p], mid + 1, r, x, val);
        pushup(p);
    }

    // 区间查询
    long long query(int p, long long l, long long r, long long ql, long long qr) {
        if (!p) return 0; // 节点不存在，说明其表示的区间全是 0
        if (ql <= l && r <= qr) return sum[p];
        long long mid = l + ((r - l) >> 1);
        long long res = 0;
        if (ql <= mid) res += query(ls[p], l, mid, ql, qr);
        if (qr > mid) res += query(rs[p], mid + 1, r, ql, qr);
        return res;
    }
};

Python

C++ 用 int& 引用出参回写根，Python 版 update 返回新根，调用方须写 seg.root = seg.update(seg.root, ...)。

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

        # 动态开点线段树：值域 [l, r] 可以很大（如 1e9），只在真正访问的位置分配节点，
# 空间 O(M log V)，M 为修改次数。
# C++ 用 int& 引用出参回写子节点指针，Python 没有引用传参，update 改为返回新子树根，
# 调用方须写 seg.root = seg.update(seg.root, l, r, x, val)。
# 节点 0 是空哨兵，ls[0] = rs[0] = sum[0] = 0，故 p == 0 表示该区间全为 0。
# 递归深度 O(log(r - l))，值域 1e18 也只有约 60 层，安全。
# C++ 的 sum 是 long long，Python int 任意精度，不存在溢出。

type NodePool = list[int]  # ls / rs / sum 这类按节点下标索引的 int 数组


class DynamicSegTree:
    """动态开点线段树，支持单点加与区间和查询。"""

    ls: NodePool  # 左儿子指针（下标），0 表示空
    rs: NodePool  # 右儿子指针（下标），0 表示空
    sum: NodePool  # 节点维护的区间和
    root: int  # 根节点下标，0 表示空树
    tot: int  # 节点分配器计数

    def __init__(self) -> None:
        # C++ 用定长 MAX_NODES 数组；Python 用动态 append，下标 0 固定为空哨兵。
        self.ls = [0]
        self.rs = [0]
        self.sum = [0]
        self.root = 0
        self.tot = 0

    def pushup(self, p: int) -> None:
        self.sum[p] = self.sum[self.ls[p]] + self.sum[self.rs[p]]

    def update(self, p: int, l: int, r: int, x: int, val: int) -> int:
        """单点加：把 x 位置加 val，返回该子树的新根（p 为 0 时会新建节点）。"""
        if p == 0:
            self.tot += 1
            p = self.tot
            self.ls.append(0)
            self.rs.append(0)
            self.sum.append(0)
        if l == r:
            self.sum[p] += val
            return p
        mid = l + ((r - l) >> 1)  # 防溢出的中点写法：l + (r-l)/2
        if x <= mid:
            self.ls[p] = self.update(self.ls[p], l, mid, x, val)
        else:
            self.rs[p] = self.update(self.rs[p], mid + 1, r, x, val)
        self.pushup(p)
        return p

    def query(self, p: int, l: int, r: int, ql: int, qr: int) -> int:
        """区间查询 [ql, qr] 的和；节点不存在说明其表示区间全是 0。"""
        if p == 0:
            return 0
        if ql <= l and r <= qr:
            return self.sum[p]
        mid = l + ((r - l) >> 1)  # 防溢出的中点写法：l + (r-l)/2
        res = 0
        if ql <= mid:
            res += self.query(self.ls[p], l, mid, ql, qr)
        if qr > mid:
            res += self.query(self.rs[p], mid + 1, r, ql, qr)
        return res

数组大小怎么开

通常在考试中，如果总操作次数为 $m$ ，值域大小上限是 $V$ ，那么最坏情况下会开辟 $m \lceil \log_2 V \rceil$ 个节点。为了安全起见，通常还会加上常数项，例如开 $m \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

        #include <iostream>
using namespace std;

struct DynamicSegTree {
    static const int MAX_NODES = 3000005; 
    int ls[MAX_NODES], rs[MAX_NODES]; 
    long long sum[MAX_NODES]; 
    int root = 0, tot = 0; 

    void pushup(int p) {
        sum[p] = sum[ls[p]] + sum[rs[p]];
    }

    void update(int &p, long long l, long long r, long long x, long long val) {
        if (!p) p = ++tot;
        if (l == r) {
            sum[p] += val;
            return;
        }
        long long mid = l + ((r - l) >> 1);
        if (x <= mid) update(ls[p], l, mid, x, val);
        else update(rs[p], mid + 1, r, x, val);
        pushup(p);
    }

    long long query(int p, long long l, long long r, long long ql, long long qr) {
        if (!p) return 0;
        if (ql <= l && r <= qr) return sum[p];
        long long mid = l + ((r - l) >> 1);
        long long res = 0;
        if (ql <= mid) res += query(ls[p], l, mid, ql, qr);
        if (qr > mid) res += query(rs[p], mid + 1, r, ql, qr);
        return res;
    }
};

int main() {
    // 例题：维护值域 [1, 10^9] 的单点修改、区间求和
    DynamicSegTree tree;
    long long limit = 1e9;
    
    // 在位置 1000 加上 5
    tree.update(tree.root, 1, limit, 1000, 5);
    // 在位置 2000000 加上 10
    tree.update(tree.root, 1, limit, 2000000, 10);
    // 在位置 999999999 加上 20
    tree.update(tree.root, 1, limit, 999999999, 20);

    // 查询区间 [1, 10000] 的和，应该只包含位置 1000 的 5
    cout << tree.query(tree.root, 1, limit, 1, 10000) << "\n"; // 输出: 5

    // 查询区间 [1, 10^9] 的和，包含所有修改，应为 35
    cout << tree.query(tree.root, 1, limit, 1, limit) << "\n"; // 输出: 35
    
    // 输出共开辟的节点数，以说明空间的高效利用
    cout << "Allocated nodes: " << tree.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
73
74
75
76
77
78

        # 动态开点线段树示例，对应同目录 example.cpp。
# 程序不读输入：在值域 [1, 1e9] 上做三次单点加，再查询两个区间。
# 不变量：下标 0 表示空节点（C++ 用 tot = 0 当 null），节点从 1 开始编号。
# 递归深度 = O(log V) ≈ 30，无需调 sys.setrecursionlimit。
# C++ 版把 3 个 3e6 长的数组当结构体成员，约 60 MB 落在栈上会爆栈；
# Python 版改用 list 动态增长，只按需分配，不会爆内存。

import sys


class DynamicSegTree:
    """区间和动态开点线段树：只在被修改的路径上建节点。"""

    def __init__(self) -> None:
        self.ls = [0]  # ls[i]：节点 i 的左孩子编号，0 表示不存在
        self.rs = [0]  # rs[i]：节点 i 的右孩子编号
        self.sum = [0]  # sum[i]：节点 i 维护的区间和
        self.root = 0
        self.tot = 0

    def pushup(self, p: int) -> None:
        self.sum[p] = self.sum[self.ls[p]] + self.sum[self.rs[p]]

    def update(self, p: int, l: int, r: int, x: int, val: int) -> int:
        """单点加 a[x] += val，返回该子树（可能新建）的根编号。

        C++ 用 int& 出参直接改指针，Python 只能把新编号返回给调用方写回。
        """
        if p == 0:
            self.tot += 1
            p = self.tot
            self.ls.append(0)
            self.rs.append(0)
            self.sum.append(0)
        if l == r:
            self.sum[p] += val
            return p
        # 写成 l + ((r - l) >> 1) 而不是 (l + r) / 2，避免值域很大时 l + r 溢出（Python 无此问题，保持同构）。
        mid = l + ((r - l) >> 1)
        if x <= mid:
            self.ls[p] = self.update(self.ls[p], l, mid, x, val)
        else:
            self.rs[p] = self.update(self.rs[p], mid + 1, r, x, val)
        self.pushup(p)
        return p

    def query(self, p: int, l: int, r: int, ql: int, qr: int) -> int:
        """区间 [ql, qr] 求和；没建过的子树贡献 0。"""
        if p == 0:
            return 0
        if ql <= l and r <= qr:
            return self.sum[p]
        mid = l + ((r - l) >> 1)
        res = 0
        if ql <= mid:
            res += self.query(self.ls[p], l, mid, ql, qr)
        if qr > mid:
            res += self.query(self.rs[p], mid + 1, r, ql, qr)
        return res


def main() -> None:
    tree = DynamicSegTree()
    limit = 10**9

    tree.root = tree.update(tree.root, 1, limit, 1000, 5)
    tree.root = tree.update(tree.root, 1, limit, 2000000, 10)
    tree.root = tree.update(tree.root, 1, limit, 999999999, 20)

    # [1, 10000] 只覆盖 1000 这个修改点。
    sys.stdout.write(str(tree.query(tree.root, 1, limit, 1, 10000)) + "\n")
    # [1, 1e9] 覆盖全部三个修改点。
    sys.stdout.write(str(tree.query(tree.root, 1, limit, 1, limit)) + "\n")
    sys.stdout.write(f"Allocated nodes: {tree.tot}\n")


if __name__ == "__main__":
    main()

测试用例

上述 example.cpp 包含了一个极端的测试，在值域高达 $10^9$ 的数组中对三个坐标 $1000$ 、 $2 \times 10^6$ 和 $999999999$ 分别加上 $5, 10, 20$ 。

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

应用分类详解

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

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

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

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

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

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

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

经典例题

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