Skip to content

可持久化线段树学习笔记

笔记约 1.5 千字
# 数据结构 # 线段树 # 可持久化线段树
检测到 KaTeX 加载失败，可能会导致文中的数学公式无法正常渲染。

本文讲述的是 可持久化权值线段树 。这种数据结构在普通线段树的基础之上支持查询某个历史版本，同时时间复杂度与线段树是同级，空间复杂度相较而言更高一些。

下文中将以「可持久化线段树」代指「可持久化权值线段树」。

注意：可持久化线段树难以进行区间修改操作，因为进行该操作可能会修改历史信息导致查询出错误结果，或者使用标记永久化避免出现这个问题，该项内容不在本文的讨论范围内。

#前置知识

#原理

可持久化线段树维护的是每个节点的历史版本，而最朴素的实现方式是每次进行修改操作都新开一颗线段树，而这样操作带来的时空复杂度是不可接受的。

稍微推导一下可以发现每次修改操作需要修改的节点个数只有 log⁡(n)\log(n) 个，那么可以使用动态开点并记录历史版本的方式来节约空间和时间的消耗，这就是可持久化线段树。

#实现

先进行离散化，以节约存储空间，具体实现不再过多描述。

然后以数值为基础建立权值线段树，维护每个数值区间中一共有多少个数。

node 类型的定义如下：

C++
1
2
3
4
5
6
7
struct node {
    int l,     // 左儿子的数组下标
        r,     // 右儿子的数组下标
        c;     // 当前区间中一共有多少个数

    node();    // 构造函数
};

这和 线段树学习笔记 中的定义有一些差别。首先，l 和 r 的存储的信息从左右端点变成了左右儿子的数组下标；其次，区间维护的信息从节点的和差与最值变成了区间中数据的个数。

再来看 build 函数。

C++
1
2
3
4
5
6
7
8
int build(int l, int r) {
    int p = ++cnt;               // 新建节点
    if (l == r) return p;        // 返回节点编号
    int mid = l + r >> 1;
    tr[p].l = build(l, mid);     // 左子树
    tr[p].r = build(mid + 1, r); // 右子树
    return p;                    // 返回节点编号
}

变化是线段树存储方式从原先的堆变成了动态开点，动态开点线段树可以在网上找到相关学习资料，在此不作过多赘述。

还有 insert 函数：

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int insert(int p, int l, int r, int x) {
    int q = ++cnt;  // 开点
    tr[q] = tr[p];  // 拷贝旧节点
    if (l == r) {
        tr[q].c++;  // 增加计数
        return q;
    }
    int mid = l + r >> 1;
    if (x <= mid) {
        tr[q].l = insert(tr[p].l, l, mid, x);     // 左子树
    } else {
        tr[q].r = insert(tr[p].r, mid + 1, r, x); // 右子树
    }
    tr[q].c = tr[tr[q].l].c + tr[tr[q].r].c;      // 更新计数（内联的 pushup 操作）
    return q;
}

仍然是动态开点，新节点的初始值由 node(l, r) 变成了 tr[p] ，即以第 i−1i - 1 个版本为基础，再进行修改。

最后是 query 函数：

C++
1
2
3
4
5
6
7
int query(int q, int p, int l, int r, int k) {
    if (l == r) return l;                   // 返回
    int c = tr[tr[q].l].c - tr[tr[p].l].c;  // 前缀和
    int mid = l + r >> 1;
    if (k <= c) return query(tr[q].l, tr[p].l, l, mid, k);  // 查询左子树
    return query(tr[q].r, tr[p].r, mid + 1, r, k - c);      // 查询右子树
}

通过 tr[tr[q].l].c - tr[tr[p].l].c 获得 [l,r][l, r] 区间内数的个数。

注：第 rr 号节点的数的个数减去第 l−1l - 1 号节点的数的个数即为 [l,r][l, r] 中的数的个数，这里使用到了前缀和的思想。

取 [l,mid][l, mid] 区间的数的个数并记为 cntcnt，接下来分两种情况：

  1. cnt≤kcnt \leq k：第 kk 小的数在左子树上。
  2. cnt>kcnt > k：第 kk 小的数在右子树上，查询右子树第 k−cntk - cnt 小的数。

递归查询即可。

#代码

对应题目：洛谷 - P3834 【模板】可持久化线段树 2 8d70723

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
#include <algorithm>
#include <iostream>
#include <vector>

using std::cin;
using std::cout;
using std::endl;

const int N = 200005;

int n, m, l, r, k, a[N];
std::vector<int> nums;

// Helpers
int find(int);

// Segment Tree
int cnt, root[N];
int build(int, int);
int insert(int, int, int, int);
int query(int, int, int, int, int);

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        nums.push_back(a[i]);
    }
    std::sort(nums.begin(), nums.end());
    nums.erase(std::unique(nums.begin(), nums.end()), nums.end());
    root[0] = build(0, nums.size() - 1);
    for (int i = 1; i <= n; i++) {
        root[i] = insert(root[i - 1], 0, nums.size() - 1, find(a[i]));
    }
    while (m--) {
        cin >> l >> r >> k;
        cout << nums[query(root[r], root[l - 1], 0, nums.size() - 1, k)] << endl;
    }
    return 0;
}

// === Helpers ===

inline int find(int x) {
    return std::lower_bound(nums.begin(), nums.end(), x) - nums.begin();
}

// === Segment Tree ===

struct node {
    int l, r, c;

    node()
        : l(0), r(0), c(0) {}
} tr[N << 5];

int build(int l, int r) {
    int p = ++cnt;
    if (l == r) return p;
    int mid = l + r >> 1;
    tr[p].l = build(l, mid);
    tr[p].r = build(mid + 1, r);
    return p;
}

int insert(int p, int l, int r, int x) {
    int q = ++cnt;
    tr[q] = tr[p];
    if (l == r) {
        tr[q].c++;
        return q;
    }
    int mid = l + r >> 1;
    if (x <= mid) {
        tr[q].l = insert(tr[p].l, l, mid, x);
    } else {
        tr[q].r = insert(tr[p].r, mid + 1, r, x);
    }
    tr[q].c = tr[tr[q].l].c + tr[tr[q].r].c;
    return q;
}

int query(int q, int p, int l, int r, int k) {
    if (l == r) return l;
    int c = tr[tr[q].l].c - tr[tr[p].l].c;
    int mid = l + r >> 1;
    if (k <= c) return query(tr[q].l, tr[p].l, l, mid, k);
    return query(tr[q].r, tr[p].r, mid + 1, r, k - c);
}

#参考资料

  1. 第 255 ~ 258 页，0x48 可持久化数据结构，《算法竞赛进阶指南》（ISBN 978-7-83009-313-6，河南电子音像出版社），李煜东，2019 年 5 月第 5 次修订版。
  2. 可持久化线段树，OI Wiki，2021 年 12 月 11 日。
  3. 可持久化线段树，维基百科，2021 年 10 月 29 日。
  4. 4.4 可持久化数据结构，AcWing 算法提高课，闫学灿，2019 年 12 月 28 日。