对于历史版本只要从根节点入手即可，在修改的过程中再把这一时间的子树建出来。
时间复杂度O（qlog(n+q)）。
1 #include<bits/stdc++.h> 2 using namespace std; 3 int cnt=0; 4 struct node 5 { 6 int l,r,v; 7 }t[20000005]; 8 int a[1000005],rt[1000005]; 9 void build(int &p,int l,int r) 10 { 11 p=++cnt;if(l==r){t[p].v=a[l];return;} 12 int m=(l+r)>>1; 13 build(t[p].l,l,m);build(t[p].r,m+1,r); 14 } 15 void change(int &p,int x,int l,int r,int pos,int num) 16 { 17 p=++cnt;t[p].l=t[x].l;t[p].r=t[x].r;t[p].v=t[x].v; 18 if(l==r){t[p].v=num;return ;} 19 int m=(l+r)>>1; 20 if(pos<=m)change(t[p].l,t[x].l,l,m,pos,num); 21 else change(t[p].r,t[x].r,m+1,r,pos,num); 22 } 23 int query(int p,int l,int r,int pos) 24 { 25 if(l==r)return t[p].v; 26 int m=(l+r)>>1; 27 if(pos<=m)return query(t[p].l,l,m,pos); 28 else return query(t[p].r,m+1,r,pos); 29 } 30 int main() 31 { 32 int n,m; 33 scanf("%d%d",&n,&m); 34 for(int i=1;i<=n;++i) 35 scanf("%d",&a[i]); 36 build(rt[0],1,n); 37 int tim,f,x,v; 38 for(int i=1;i<=m;++i) 39 { 40 scanf("%d%d",&tim,&f); 41 if(f==1){scanf("%d%d",&x,&v);change(rt[i],rt[tim],1,n,x,v);} 42 else {scanf("%d",&x);printf("%d ",query(rt[tim],1,n,x));rt[i]=rt[tim];} 43 } 44 return 0; 45 }