[模板]可持久化数组

# 历史版本数组的模板 ```cpp #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; } ```