不断开辟新的节点，存储新状态下改变的点，不改变的点直接回历史中去找，相当于新存变化的节点，不变的节点共用。
可持久化线段树 1
时间数组下标维护的是根节点。在根节点建树，不变的部分直接指向原先的子树即可。
代码
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<vector>
#include<random>
#include<ctime>
using namespace std;
long long r_r(){//快读
long long k=0,f=1;
char c=getchar();
while(!isdigit(c)){
if(c=='-')f=-1;
c=getchar();
}
while(isdigit(c)){
k=(k<<1)+(k<<3)+(c^48);
c=getchar();
}
return k*f;
}
const int o_o=1e6+10;
int a_a[o_o],n,q,a_s[o_o<<5],m;
struct po{
int l,r;//左右儿子
int v;//节点价值
}t_r[o_o<<5];
int x_p;
void b_t(int &k,int l,int r){
k=++x_p;//分配节点编号
if(l==r){//是子叶
t_r[k].v=a_a[l];//节点赋值
return;
}
int m_i=(l+r)>>1;
b_t(t_r[k].l,l,m_i);//左子树
b_t(t_r[k].r,m_i+1,r);//右子树
}
void g_a(int &k,int l_s,int l,int r,int q,int v){
k=++x_p;//分配新节点
t_r[k].l=t_r[l_s].l;//继承历史节点信息
t_r[k].r=t_r[l_s].r;
t_r[k].v=t_r[l_s].v;
if(l==r){//是叶节点
t_r[k].v=v;//更改新值
return;
}
int m_i=(l+r)>>1;
if(q<=m_i)g_a(t_r[k].l,t_r[l_s].l,l,m_i,q,v);//目标点在左子树
else g_a(t_r[k].r,t_r[l_s].r,m_i+1,r,q,v);//目标点在右子树
}
int f_i(int k,int l,int r,int q){
if(l==r)return t_r[k].v;//找到叶节点
int m_i=(l+r)>>1;
if(q<=m_i)return f_i(t_r[k].l,l,m_i,q);//目标节点在左子树
else return f_i(t_r[k].r,m_i+1,r,q);//目标节点在右子树
}
int main(){
n=r_r();m=r_r();
for(int i=1;i<=n;i++)a_a[i]=r_r();//读入原序列
b_t(a_s[0],1,n);//建树（0 的历史状态根节点为 0）
for(int i=1;i<=m;i++){
int l_s=r_r(),op=r_r(),x=r_r();
if(op==1){
int v=r_r();
//当前值，历史值，左端点，右端点，要改的位置，改成的值
g_a(a_s[i],a_s[l_s],1,n,x,v);//修改值
}
if(op==2){
printf("%d\n",f_i(a_s[l_s],1,n,x));//查询节点信息
a_s[i]=a_s[l_s];//直接复制历史信息（完全一样的版本）
}
}
return 0;
}可持久化线段树 2
每插入一个数，存一次线段树的状态。时间变成了插入的顺序，这样查 $[l,r]$ 区间第 $k$ 大时，找到 $l-1$，$r$ 为根的线段树，相减，剩下的树中的数就是 $[l,r]$ 中的所有数。直接查排名即可。（插入数的时候要根据平衡树的特性插，这样查询的时候，就是平衡树查排名。）
注意：由于本题的值域过大，所以要离散化。
代码
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<set>
#include<queue>
#include<vector>
#include<bitset>
#include<map>
#include<utility>
#include<random>
#include<ctime>
using namespace std;
int r_r(){//快读
int x=0,f=1;
char c=getchar();
while(!isdigit(c)){
if(c=='-')f=-1;
c=getchar();
}
while(isdigit(c)){
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
const int o_o=1e6+10;
int x_p;//节点编号
int n,m;
struct po{
int s_m;//子树大小
int l,r;//左右节点
}t_r[o_o<<5];
int g_g[o_o];//每个时刻线段树的根节点
int a_a[o_o],s_a[o_o];//原序列，离散化后的序列
void b_t(int &k,int l,int r){
k=++x_p;//新节点编号
if(l==r)return;//叶子结点返回
int m_i=(l+r)>>1;
b_t(t_r[k].l,l,m_i);//左子树
b_t(t_r[k].r,m_i+1,r);//右子树
}
int a_d(int k,int l,int r,int x_x){
int n=++x_p;//新节点标号
t_r[n].l=t_r[k].l;//记录上个状态左右儿子
t_r[n].r=t_r[k].r;//记录上个状态左右儿子
t_r[n].s_m=t_r[k].s_m+1;//每次比上次多加一个点
if(l==r)return n;//叶子结点，没有子树返回
int m_i=(l+r)>>1;
if(x_x<=m_i)t_r[n].l=a_d(t_r[n].l,l,m_i,x_x);//目标在左子树
else t_r[n].r=a_d(t_r[n].r,m_i+1,r,x_x);//目标在右子树
return n;//返回节点编号
}
int f_i(int t_1,int t_2,int l,int r,int k){
int a_s;
int m_i=((l+r)>>1);
int x=t_r[t_r[t_2].l].s_m-t_r[t_r[t_1].l].s_m;//从 t_2 状态减去 t_1-1 后，剩下的元素直接查排名即可
if(l==r)return l;//叶子结点，找到目标，返回
if(x>=k)a_s=f_i(t_r[t_1].l,t_r[t_2].l,l,m_i,k);//在左子树中
else a_s=f_i(t_r[t_1].r,t_r[t_2].r,m_i+1,r,k-x);//在右子树中
return a_s;//返回结果
}
int main(){
n=r_r(),m=r_r();
for(int i=1;i<=n;i++){
a_a[i]=r_r();//读入原序列
s_a[i]=a_a[i];//初始化离散序列
}
sort(s_a+1,s_a+n+1);//离散序列排序
int l_n=unique(s_a+1,s_a+n+1)-s_a-1;//去重后的长度
b_t(g_g[0],1,l_n);//建树
for(int i=1;i<=n;i++){
int x_x=lower_bound(s_a+1,s_a+l_n+1,a_a[i])-s_a;//当前数在整个序列中的排名
g_g[i]=a_d(g_g[i-1],1,l_n,x_x);//存储更节点编号
}
while(m--){//询问
int l=r_r(),r=r_r(),k=r_r();
int a_s=f_i(g_g[l-1],g_g[r],1,l_n,k);//查寻结果
printf("%d\n",s_a[a_s]);//在离散化后的数组中找答案
}
return 0;
}高级打字机
存每一个字符插入后的变化新树，回撤操作直接访问里历史根节点即可，查找字符直接找排名找值即可。
代码
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<vector>
#include<random>
#include<ctime>
using namespace std;
long long r_r(){
long long k=0,f=1;
char c=getchar();
while(!isdigit(c)){
if(c=='-')f=-1;
c=getchar();
}
while(isdigit(c)){
k=(k<<1)+(k<<3)+(c^48);
c=getchar();
}
return k*f;
}
const int o_o=1e6+10;
int m,x_p=1,z_g;
int g_g[o_o];
struct po{
int l;
int r;
char v;
int s_z;
}t_r[o_o<<2];
void u_p(int k){//更新子树大小
t_r[k].s_z=t_r[t_r[k].l].s_z+t_r[t_r[k].r].s_z;
}
void c_a(int &k,int l_s,int l,int r,char x){
if(l>r) return;//超出范围，退出
k=++x_p;//变新节点
t_r[k].l=t_r[l_s].l;//继承这个节点的状态
t_r[k].r=t_r[l_s].r;
t_r[k].s_z=t_r[l_s].s_z;
t_r[k].v=t_r[l_s].v;
if(l==r){//子叶，记录新字符状态
t_r[k].v=x;//记录新字符
t_r[k].s_z=1;//更新子树大小
return;
}
int m_i=(l+r)>>1;
if(t_r[t_r[k].l].s_z==m_i-l+1)//左子树满了
c_a(t_r[k].r,t_r[l_s].r,m_i+1,r,x);//插到右子树
else c_a(t_r[k].l,t_r[l_s].l,l,m_i,x);//左子树没满
u_p(k);//更新节点信息
}
char g_a(int k,int l,int r,int x){//在当前子树中找排名
if(l==r)return t_r[k].v;//找到节点
int m_i=(l+r)>>1;
if(x<=t_r[t_r[k].l].s_z)//左子树能包含这种情况
return g_a(t_r[k].l,l,m_i,x);
else//在右子树找
return g_a(t_r[k].r,m_i+1,r,x-t_r[t_r[k].l].s_z);
}
int main(){
m=r_r();
for(int i=1;i<=m;i++){
char op,c;
int x;
cin>>op;
if(op=='T'){
cin>>c;
++z_g;//更新总操作数
c_a(g_g[z_g],g_g[z_g-1],1,m,c);//插入字符
}else if(op=='U'){
x=r_r();
++z_g;//更新总操作数
g_g[z_g]=g_g[z_g-x-1];//返回历史状态
}else if(op=='Q'){
x=r_r();
cout<<g_a(g_g[z_g],1,m,x)<<endl;//输出当前转态字符
}
}
return 0;
}
