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

一句话算法

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

问题模型

给定一个值域区间非常大（例如 $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$ ，空间是完全可以承受的。

代码模板

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

数组大小怎么开

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

代码实现

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

测试用例

上述 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 时动态开点下放标记）。