主席树，又名可持久化线段树，可以访问多个历史版本的树上存的信息。
图及其他来源于此：https://www.cnblogs.com/hyfhaha/p/10678275.html
基本思想
用到的基本思想就是对于每一个修改版本的树，只新建修改后的节点，如果是每一个版本新开一个线段树的话空间一定不够。
这是普通的线段树单点修改。
这是主席树的单点修改。
几个月前我被这个东西劝退了，但现在来看挺好理解的，无非就是把修改的点从下到上涉及到的值有变化的点新开一个点，然后对于一些有没有变化的点，直接和修改后的连起来即可，根据根节点的不同可以判断是那个版本的点。
P3919 【模板】可持久化线段树 1（可持久化数组）
这个题目就是单点修改单点查询，可以配合代码以及注释理解一下。
#include<bits/stdc++.h>
#define N 1000010
using namespace std;
int a[N],n,m,q,rt[N*30];//a存放输入的每一个点的值，rt存放每一个版本的根节点
int ls[N*30],rs[N*30],val[N*30],cnt;//存放每一个节点的左右儿子，值
inline int read(){int x=0,f=1;char ch=getchar();while(!isdigit(ch)){f=ch!='-';ch=getchar();}while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return f?x:-x;}
inline void build(int &x,int l,int r)//建树
{
x=++cnt;//存编号
if(l==r){val[x]=a[l];return ;}//如果到了叶子节点就直接赋值退出
int mid=(l+r)>>1;//计算mid的值
build(ls[x],l,mid);//递归建左子树
build(rs[x],mid+1,r);//递归建右子树
}
inline void ins(int &x,int pre,int l,int r,int q,int v)//在某个版本修改某个值
{
x=++cnt;ls[x]=ls[pre];rs[x]=rs[pre];val[x]=val[pre];//复制节点
if(l==r){val[x]=v;return ;}//修改当前节点的值
int mid=(l+r)>>1;//计算mid的值
if(q<=mid)ins(ls[x],ls[pre],l,mid,q,v);//根据版本去修改
else ins(rs[x],rs[pre],mid+1,r,q,v);
}
inline int sum(int x,int l,int r,int q)//区间求值
{
if(l==r)return val[x];//如果当前点就是要差查的值就直接返回
int mid=(l+r)>>1;//计算mid的值
if(q<=mid)return sum(ls[x],l,mid,q);//按编号查询
else return sum(rs[x],mid+1,r,q);
}
int main()
{
n=read();m=read();
for(int i=1;i<=n;i++)a[i]=read();
build(rt[0],1,n);//建树，初始版本号：0
for(int i=1;i<=m;i++)//m次操作，m个新版本
{
int pre=read(),op=read(),x=read();//输入版本号，操作，序号
if(op==1){int v=read();ins(rt[i],rt[pre],1,n,x,v);}//操作一，修改值
else {cout<<sum(rt[pre],1,n,x)<<endl;rt[i]=rt[pre];}
}
return 0;//好习惯
}
P3834 【模板】可持久化线段树 2
这题我们需要考虑主席树
首先我们可以想到，我们先从小到大排序离散化一下，然后我们可以一个一个把数插入到主席树上，一共是 \(n\) 个版本，然后第 \(i\) 个版本代表的是前 \(i\) 个数在数列中的排名情况，然后对于 \(l\) 到 \(r\) 之间的点我们可以直接用前缀和思想，用 \(i\) 版本减去 \(i-1\) 版本的树上节点就可以了。
#include<bits/stdc++.h>
#define N 1000100
#define endl '\n'
using namespace std;
int n,m,rt[N],ls[N<<5],rs[N<<5];
int cnt,b[N],a[N],val[N<<5];
inline int read(){int x=0,f=1;char ch=getchar();while(!isdigit(ch)){f=ch!='-';ch=getchar();}while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return f?x:-x;}
inline void build(int &x,int l,int r)
{
x=++cnt;
if(l==r)return ;
int mid=(l+r)>>1;
build(ls[x],l,mid);
build(rs[x],mid+1,r);
}
inline void add(int &x,int pre,int l,int r,int p)
{
x=++cnt;ls[x]=ls[pre];rs[x]=rs[pre];val[x]=val[pre]+1;
if(l==r)return ;
int mid=(l+r)>>1;
if(p<=mid)add(ls[x],ls[pre],l,mid,p);
else add(rs[x],rs[pre],mid+1,r,p);
}
inline int ask(int u,int v,int l,int r,int k)
{
if(l==r)return b[l];
int mid=(l+r)>>1;
int num=val[ls[v]]-val[ls[u]];
if(num>=k)return ask(ls[u],ls[v],l,mid,k);
else return ask(rs[u],rs[v],mid+1,r,k-num);
}
signed main()
{
n=read();m=read();
for(int i=1;i<=n;i++)b[i]=a[i]=read();
sort(b+1,b+n+1);
int len=unique(b+1,b+n+1)-b-1;
build(rt[0],1,len);
for(int i=1;i<=n;i++)
{
int x=lower_bound(b+1,b+len+1,a[i])-b;
add(rt[i],rt[i-1],1,len,x);
}
for(int i=1;i<=m;i++)
{
int l=read(),r=read(),x=read();
cout<<ask(rt[l-1],rt[r],1,len,x)<<endl;
}
return 0;
}