代碼

//可持久化線段樹 #include <cstdio> using namespace std;struct node {node *Lnode,*Rnode;int val;void clone(node* N){Lnode=N->Lnode;Rnode=N->Rnode;val=N->val;return;} }tree[20000005],*root[1000005],*tail=tree; int a[1000005];node* build(int L,int R) {node *N=(++tail);if(L==R){N->val=a[L];return N;}int M=(L+R)>>1;N->Lnode=build(L,M);N->Rnode=build(M+1,R);return N; }node* modify(node* N,int L,int R,int pos,int val) {node *O=(++tail);O->clone(N);if(L==R){O->val=val;return O;}int M=(L+R)>>1;if(pos<=M) O->Lnode=modify(N->Lnode,L,M,pos,val);else O->Rnode=modify(N->Rnode,M+1,R,pos,val);return O; }int query(node* N,int L,int R,int pos) {if(L==R) return N->val;int M=(L+R)>>1;if(pos<=M) return query(N->Lnode,L,M,pos);return query(N->Rnode,M+1,R,pos); }int main() {int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) scanf("%d",&a[i]);root[0]=build(1,n);for(int i=1;i<=m;i++){int v,opt,loc;scanf("%d%d%d",&v,&opt,&loc);if(opt==1){int val;scanf("%d",&val);root[i]=modify(root[v],1,n,loc,val);}else{printf("%d\n",query(root[v],1,n,loc));root[i]=root[v];}}return 0; }

轉載于:https://www.cnblogs.com/C-C-C-P/p/10393681.html

總結

以上是生活随笔為你收集整理的LGOJ P3919【模板】可持久化数组（可持久化线段树/平衡树）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。