基本模板，就是每次修改再建立一个根节点，然后将要修改的部分建立新节点；之后每次询问就从提问的那个root去进行线段树上的查找即可
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=4e7+5;
const int maxm=1e6+5;
int n,m,cnt,root[maxn],a[maxm];
struct tree
{int l,r,val;
}tr[maxn];
int build(int now,int l,int r)
{now=++cnt;if(l==r){tr[now].val=a[l];return cnt;}int mid=(l+r)>>1;tr[now].l=build(tr[now].l,l,mid);tr[now].r=build(tr[now].r,mid+1,r);return now;
}
int update(int now,int l,int r,int x,int val)
{cnt++; tr[cnt]=tr[now]; now=cnt;if(l==r){tr[now].val=val;return now;}int mid=(l+r)>>1;if(x<=mid) tr[now].l=update(tr[now].l,l,mid,x,val);else tr[now].r=update(tr[now].r,mid+1,r,x,val);return now;
}
int query(int now,int l,int r,int x)
{if(l==r) return tr[now].val;int mid=(l+r)>>1;if(x<=mid) return query(tr[now].l,l,mid,x);else return query(tr[now].r,mid+1,r,x);
}
int main()
{freopen("a.in","r",stdin);freopen("a.out","w",stdout);scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) scanf("%d",&a[i]);root[0]=build(0,1,n);int x,y,z,op;for(int i=1;i<=m;i++){scanf("%d%d",&x,&op);if(op==1){scanf("%d%d",&y,&z);root[i]=update(root[x],1,n,y,z);}else{scanf("%d",&y);printf("%d\n",query(root[x],1,n,y));root[i]=root[x];}}return 0;
}