介绍

主席树即可持久化线段树，由 hjt 大佬发明。
好像又称函数式线段树。
可以查询序列在任意时间的历史状态。
学习链接 学习链接

主要思路

维护历史状态，若采用直接拷贝整棵树的方式，空间爆炸。
可以发现每次修改只有部分节点发生了改变（其实就是到树根那条链会改变），因此每次只需要记录下来这条链的变化即可。具体来说，相比拷贝整棵树，优化的地方是将新树与旧树没有修改的部分合并，因此只新增加了一条链，空间复杂度 \(O(n \log n)\)。

例题一

P3834 【模板】可持久化线段树 2

思路

可持久化权值线段树，用主席树维护即可。

代码

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

const int N = 2e5+5;

int n,m,a[N],root[N];
struct node
{
    int l,r,sum;
}t[N<<5]; //主席树需要开32倍空间
int tot;

int insert(int k,int l,int r,int x,int v)
{
    int p = ++tot;
    t[p] = t[k]; //复制原树
    if (l == r) {t[p].sum += v;return p;}
    int mid = l + r >> 1;
    if (x <= mid) t[p].l = insert(t[k].l,l,mid,x,v); //更新链
    else t[p].r = insert(t[k].r,mid + 1,r,x ,v);
    t[p].sum = t[t[p].l].sum + t[t[p].r].sum; //pushup
    return p;
}
int query(int p,int q,int l,int r,int x)
{
    if (l == r) return l;
    int mid = l + r >> 1;
    int cnt = t[t[p].l].sum-t[t[q].l].sum ; // 值域 l ~ r 中数的个数 
    if (x <= cnt) return query(t[p].l,t[q].l,l,mid,x);
    else return query(t[p].r,t[q].r,mid + 1,r,x-cnt);
}
int main()
{
    cin >> n >> m;
    vector<int> v;
    for (int i = 1;i <= n;i++) cin >> a[i],v.push_back(a[i]);
    //离散化
    sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end());
    for (int i= 1; i<= n;i++) a[i] = lower_bound(v.begin(),v.end(),a[i]) - v.begin() + 1;
    const int T = v.size() + 10; //值域范围
    //root[i] 指 第 i 个版本的根
    for (int i = 1;i <= n;i++) root[i] = insert(root[i-1],1,T,a[i],1);
    for (int i = 1;i  <= m;i++) 
    {
        int l,r,k;cin >> l >>r >> k;
        //第 i 个版本保存了 1~i 的数的贡献
        //因为主席树满足可减性
        //因此用第 r 个版本 减去 第 l-1 个版本 可以得到 l~r的贡献
        cout << v[query(root[r],root[l-1],1,T,k)-1] << endl;
    }
    return 0;
}

例题二

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

思路

主席树维护数组的模板，需要支持修改和查询历史版本的数组。

// Problem: P3919 【模板】可持久化线段树 1（可持久化数组）
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3919
// Memory Limit: 1024 MB
// Time Limit: 1500 ms
// Author: Eason
// Date:2024-03-26 21:44:45
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define ll long long
#define INF 0x3f3f3f3f
#define re register
#define il inline
#define gc getchar
inline int read()
{
	int f=1,k=0;
	char c = getchar();
	while (c <'0' || c > '9')
	{
		if (c=='-') f=-1;
		c=getchar();
	}
	while(c >= '0' && c <= '9')  k = (k << 1)+(k << 3)+(c^48),c=getchar();
	return k*f;
}

const int N = 1e6+5;

int a[N],n,m,root[N];

struct node
{
	int l,r,val;
}t[N << 5];
int tot;
int build(int l,int r) //建树
{
	int p = ++tot;
	if (l == r) {t[p].val = a[l];return p;}
	int mid = l + r >> 1;
	t[p].l = build(l,mid);
	t[p].r = build(mid + 1,r);
	return p; 
}

int insert(int k,int l,int r,int x,int v)
{
	int p = ++tot;
	t[p] = t[k]; //复制原节点
	if (l == r) // 即没有儿子
	{
		t[p].val = v;//直接赋值
		return p;
	}
	int mid =  l + r >> 1;
	if (x <= mid) t[p].l = insert(t[k].l,l,mid,x,v);
	else t[p].r = insert(t[k].r,mid + 1,r,x,v);
	return p;
}

int query(int k,int l,int r,int x) //查询
{
	if (x < l || x > r) return 0;
	if (l == r) return t[k].val;
	int mid = l + r >> 1;
	return query(t[k].l,l,mid,x) + query (t[k].r,mid + 1,r,x);
}

int main()
{
	cin >> n >> m;
	for (int i = 1;i <= n;i++) a[i] = read();
	root[0] = build(1,n);
	for (int i = 1;i <= m;i++)
	{
		int x = read(),op = read(),y = read();
		if (op == 1)
		{
			int z = read();
			root[i] = insert(root[x],1,n,y,z);
		}
		else
		{
			printf("%d\n",query(root[x],1,n,y));
			root[i] = root[x];
		}
	}
	return 0;
}