此外，每进行一次操作，就会生成一个新的版本。

版本编号即为当前操作的编号（从

开始编号，版本

2，即为生成一个完全一样的版本，不作任何改动。

即，询问生成的版本是询问所访问的那个版本的复制。

对于

&now){now=++cnt;if(l==r){***[now].val=a[l];return;}int

m=(l+r)>>1;build(l,m,***[now].l);build(m+1,r,***[now].r);

//main函数内部

i=1;i<=n;i++){cin>>a[i];

build(1,n,root[0]);

先初始化，开始建树，建树过程与正常线段树区别不大

&num){***[now=++cnt]=***[ver];if(l==r){***[now].val=num;return;}int
mid=(l+r)>>1;if(pos<=mid)modify(l,mid,***[ver].l,***[now].l,pos,num);else
modify(mid+1,r,***[ver].r,***[now].r,pos,num);
int
mid=(l+r)>>1;if(pos<=mid)return
query(l,mid,***[now].l,pos);else
return
v,opt,x,y;cin>>v>>opt;switch(opt){case
1:cin>>x>>y;modify(1,n,root[v],root[i],x,y);break;case
2:cin>>x;cout<<query(1,n,root[v],x)<<"\n";root[i]=root[v];break;}

modify()与可持久化线段树/主席树的modify()函数类似，先复制前一个版本，后续逐个修改不一样的节点

main()函数只需要判断opt然后接着调用即可