主席树/可持久化线段树 学习笔记

medal_dreams · 2026-04-18 20:01:03 · 算法·理论

可能另一种阅读体验

update：

2026.4.22：被第一次打回，修改错误。\ 2026.4.24：被第二次打回，修改错误，重新提交审核，管理员辛苦了。

定义

我们引用一下 OI Wiki 的定义：

可持久化数据结构（Persistent data structure）总是可以保留每一个历史版本，并且支持操作的不可变特性（immutable）。 ——OI Wiki

故可持久化线段树就是可以存储多个历史版本，并且进行一些操作的线段树。

用途

可持久化线段树是很多可持久化数据结构的起点，它允许查询，修改某一版本的某一值，或者查询静态区间第 k 小。

值得一提的是，允许访问或修改所有版本的可持久化叫做完全可持久化。\ 详见：可持久化数据结构简介 - OI Wiki。

基础实现

对于多个版本，我们很明显可以对于每一个版本建一个线段树，但是这样，我们的空间会爆炸！

故我们考虑让前面的版本对当前版本有一定贡献，考虑对于每一个版本，有以下两种情况：

1. 如果不需要修改节点，我们就让指针指向上一个版本的这个未修改节点。
2. 如果是需要修改节点，我们就对其新建一个节点。\ 如图：\

其实现依赖于用结构体维护 ls, rs，并且对于一个新节点，我们先让其等于原节点，并且给其一个新的编号，再依次更新下面的节点。

代码如下：

struct node{
    int val, ls, rs;
}nd[N << 7];
#define ls(k) nd[k].ls
#define rs(k) nd[k].rs
int newnode(int p){nd[++ tot] = nd[p];return tot;}

修改操作

可见，因为每一个要修改的节点需要有一个新的编号，所以我们需要让这个应修改节点变为这个编号，其实现方法即为在 update 操作中将引入 p 编号的节点加上址传递，即加上取地址符 &。其他和普通线段树没有什么很大的差异。

代码如下：

void update(int &p, int l, int r, int x, int val)
{
    p = newnode(p);//变为新编号
    if(l == r){nd[p].val = val;return ;}//更新值
    int mid = l + r >> 1;
    if(x <= mid) update(ls(p), l, mid, x, val);
    else update(rs(p), mid + 1, r, x, val);
    //pushup(p);
     //pushup 操作看题，可有可无
}

查询操作

因为所有版本我们已经处理好了，直接查询即可。当然，你也可以使用可持久化数组。

代码如下：

ll query(int p, int l, int r, int x)
{
    if(l == r) return nd[p].val;
    int mid = l + r >> 1;
    if(x <= mid) return query(ls(p), l, mid, x);
    else return query(rs(p), mid + 1, r, x);
}

基础实现例题

1. P3919 【模板】可持久化线段树 1（可持久化数组）

简要题意：

维护一个长度为 n 的数组 a，进行 m 次以下操作：

1. 形如 v 1 p c 表示把版本 v 的 a_p 改为 c。
2. 形如 v 2 p 输出版本 v 的 a_p。

对于每个操作，都会生成一个对应的版本。

其中 1 \le n,m \le 10 ^ 6，1 \le p \le n，-10^9 \le a_i,c \le 10^9。\ 如果当前是第 x 次操作，则 0 \le v < x。\ 版本 0 为原始数组。

思路

按照上面代码和思想，模拟即可。

:::success[代码]

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int N = 1e6 + 66;
int root[N], tot;
struct Seg_Ment_Tree{
    struct node{
        int val, ls, rs;
    }nd[N << 7];
    #define ls(k) nd[k].ls
    #define rs(k) nd[k].rs
    int newnode(int p){nd[++ tot] = nd[p];return tot;}
    void update(int &p, int l, int r, int x, int val)
    {
        p = newnode(p);
        if(l == r){nd[p].val = val;return ;}
        int mid = l + r >> 1;
        if(x <= mid) update(ls(p), l, mid, x, val);
        else update(rs(p), mid + 1, r, x, val);
    }
    ll query(int p, int l, int r, int x)
    {
        if(l == r) return nd[p].val;
        int mid = l + r >> 1;
        if(x <= mid) return query(ls(p), l, mid, x);
        else return query(rs(p), mid + 1, r, x);
    }
}seg;
int n, m, a;
int main()
{
    ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for(int i = 1;i <= n;i ++) cin >> a, seg.update(root[0], 1, n, i, a);//初始化初始版本（即原数组）
    for(int i = 1;i <= m;i ++)
    {
        int od, v, p, c;
        cin >> v >> od >> p;
        root[i] = root[v];//当前版本为给定版本
        if(od == 1)
        {
            cin >> c;
            seg.update(root[i], 1, n, p, c);//修改
        }
        else cout << seg.query(root[i], 1, n, p) << '\n';
    }
    return 0;
}

:::

2. P1383 高级打字机

简要题意：

开始有一空串，要进行 n 次以下操作：

1. 形如 T x，表示在后面加入一字符 x。
2. 形如 U x，表示撤销 x 次除操作三的操作。
3. 形如 Q x 表示查询当前字符串的第 x 个字符。