历史版本数组的模板

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000010;
int n,m;
int a[maxn];
int T[maxn];
namespace ZXTree{
    int totID = 0;
    int L[maxn << 5],R[maxn << 5],sumv[maxn << 5];
    int build(int l,int r){
        int id = ++totID;
        int mid = l + r >> 1;
        if(l != r){
            L[id] = build(l,mid);
            R[id] = build(mid+1,r);
        }
        if(l == r) sumv[id] = a[l];
        return id;
    }
    int update(int preID,int l,int r,int x,int v){
        int id = ++totID;
        int mid = l + r >> 1;
        L[id] = L[preID],R[id] = R[preID];
        if(l != r){
            if(x <= mid) L[id] = update(L[id],l,mid,x,v);
            else R[id] = update(R[id],mid+1,r,x,v);
        }
        if(l == r) sumv[id] = v;
        return id;
    }
    int query(int verID,int l,int r,int x){
        if(l == r) return sumv[verID];
        int mid = l + r >> 1;
        if(x <= mid) return query(L[verID],l,mid,x);
        else return query(R[verID],mid+1,r,x);
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",a+i);
    T[0] = ZXTree::build(1,n);
    for(int i=1;i<=m;i++){
        int ver,ac,loc,val;
        scanf("%d%d%d",&ver,&ac,&loc);
        if(ac == 1){
            scanf("%d",&val);
            T[i] = ZXTree::update(T[ver],1,n,loc,val);
        }else{
            int ans = ZXTree::query(T[ver],1,n,loc);
            printf("%d\n",ans);
            T[i] = ZXTree::update(T[ver],1,n,loc,ans);
        }
    }
    return 0;
}