我校本周讲课中讲了平衡树和可持久化线段树，我平衡树还没学清楚，那我们先学习一下可持久化线段树
题面https://www.luogu.org/problemnew/show/P3919
维护两个操作
操作一：在某个历史版本上修改某个点的值
操作二：在某个历史版本上查询某个点的值
第一反应就是n棵线段树直接干下去，然后tle，mle套餐欢迎你
仔细思考一下，我修改单点的值，只会修改根到该点的log个节点，那么我只要新开log个节点记录下更改后的值即可
ps：这里我一开始没有想通，手画一张图后发现每个节点可能有多个父亲，但一定只有两个儿子（有可能为空），然后从每一版本的根遍历整棵线段树就是当时修改后的线段树
那么这个问题就迎刃而解了，再有问题就看代码就好了
#include<bits/stdc++.h> using namespace std; inline int read(){ int w=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9'){ w=(w<<3)+(w<<1)+ch-48; ch=getchar(); } return w*f; } int n,m,root[2000010],a[2000010],tot; struct node{ int ls,rs,val; }st[20000010]; inline int build(int l,int r){ int pos=tot++;//先开一个节点 if(l==r){ st[pos].val=a[l];return pos;//更新到了叶子节点 } int mid=(l+r)>>1; st[pos].ls=build(l,mid); st[pos].rs=build(mid+1,r); return pos; } /* 这里写一点关于自己对可持久化操作的理解，既然是要不断向后新开节点，那么正常的p<<1和p<<1|1就不能 正常使用了，那么在建树和更新的过程中都要不断返回新的节点编号，用于更新父亲节点的左儿子或右儿子 */ inline int update(int tim,int l,int r,int p,int k){//tim表示原版本，l，r为范围，p为修改位置，k为修改端点 int pos=tot++;//新开节点 if(l==r){//到叶子了，大力返回 st[pos].val=k;return pos; } st[pos]=st[tim];//新的节点可以复制原节点的信息然后再更新 int mid=(l+r)>>1; if(p<=mid) st[pos].ls=update(st[tim].ls,l,mid,p,k);//新版本的左儿子修改 else st[pos].rs=update(st[tim].rs,mid+1,r,p,k);//新版本的右儿子修改 return pos;//一定要返回当前节点的编号 } inline int found(int tim,int l,int r,int p){//tim表示版本，l，r为范围，p为我们要查询的位置 if(l==r) return st[tim].val;//找到了叶子节点，返回当前值 int mid=(l+r)>>1; if(p<=mid) return found(st[tim].ls,l,mid,p);//往左儿子找 else return found(st[tim].rs,mid+1,r,p);//往右儿子找 } int main(){ n=read();m=read();int i,j,k; for(i=1;i<=n;i++) a[i]=read(); build(1,n);//建树 int x,y,z,type; for(i=1;i<=m;i++){//按题目要求进行操作 x=read();type=read();y=read(); if(type==1){ z=read(); root[i]=update(root[x],1,n,y,z); } else{ root[i]=root[x]; int ans=found(root[x],1,n,y); printf("%d ",ans); } } return 0; }