可持久化线段树（主席树）

代码

#include<bits/stdc++.h>
using namespace std;
const int N=4e7+10;
int n,m,t,top,rt,mode,x,y;
int f[N],a[N],root[N];
struct kkk{
    int l,r,val;
}tree[N];
int clone(int node){
    top++;
    tree[top]=tree[node];
    return top;
}
int maketree(int node,int begin,int end){
    node=++top;
    if(begin==end){
        tree[node].val=a[begin];
        return top;
    }
    int mid=begin+end>>1;
    tree[node].l=maketree(tree[node].l,begin,mid);
    tree[node].r=maketree(tree[node].r,mid+1,end);
    return node;
}
int update(int node,int begin,int end,int x,int val){
    node=clone(node);
    if(begin==end) tree[node].val=val;
    else{
        int mid=begin+end>>1;
        if(x<=mid) tree[node].l=update(tree[node].l,begin,mid,x,val);
        else tree[node].r=update(tree[node].r,mid+1,end,x,val);
    }
    return node;
}
int query(int node,int l,int r,int x){
    if(l==r) return tree[node].val;
    else{
        int mid=l+r>>1;
        if(x<=mid) return query(tree[node].l,l,mid,x);
        else return query(tree[node].r,mid+1,r,x);
    }
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;++i) cin>>a[i];
    root[0]=maketree(0,1,n);
    for(int i=1;i<=m;++i){
        cin>>rt>>mode>>x;
        if(mode==1){
            cin>>y;
            root[i]=update(root[rt],1,n,x,y);
        }
        else{
            cout<<query(root[rt],1,n,x)<<'\n';
            root[i]=root[rt];
        }
    }
    return 0;
}