可持久化线段树模板(洛谷3919查询历史版本)
代码:
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 4;
struct T {
int l,r,v;
}t[maxn*40];
int a[maxn],edition[maxn*40],tot;
int build(int l,int r)
{
int p=++tot;
if(l==r) {
t[p].v=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 update(int id,int l,int r,int k,int val)
{
int p=++tot;
if(l==r) {
t[p].v=val; return p;
}
int mid=(l+r)>>1;
t[p].l=t[id].l,t[p].r=t[id].r;
if(k<=mid) t[p].l=update(t[p].l,l,mid,k,val);
else t[p].r=update(t[p].r,mid+1,r,k,val);
return p;
}
int query(int id,int l,int r,int k)
{
if(l==r) return t[id].v;
int mid=(l+r)>>1;
if(k<=mid) return query(t[id].l,l,mid,k);
else return query(t[id].r,mid+1,r,k);
}
int main()
{
int n,m,id,op,k,val;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
build(1,n);
edition[0]=1;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&id,&op,&k);
if(op==1) {
scanf("%d",&val);
edition[i]=update(edition[id],1,n,k,val);
}
else {
edition[i]=edition[id];
printf("%d\n",query(edition[id],1,n,k));
}
}
return 0;
} 
