可持久化数组

洛谷 可持久化数据结构 线段树

洛谷模板题

题目描述
如题，你需要维护这样的一个长度为 $N$ 的数组，支持如下几种操作

1.在某个历史版本上修改某一个位置上的值

2.访问某个历史版本上的某一位置的值

此外，每进行一次操作（对于操作2，即为生成一个完全一样的版本，不作任何改动），就会生成一个新的版本。版本编号即为当前操作的编号（从1开始编号，版本0表示初始状态数组）

直接使用主席树维护就可以了，似乎会比用平衡树维护常数小

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN = 1000000+9;
int n,m;
int num[MAXN];
int rt[MAXN];
struct T{
    int ls,rs;
    int val;
}tree[MAXN*21];
int cnt;
void update(int x){
    //nothing to do ...
}
int Build(int l,int r){
    int now=++cnt;
    if(l==r){
        tree[now].val=num[l];
        return now;
    }
    int mid=l+r>>1;
    tree[now].ls=Build(l,mid);
    tree[now].rs=Build(mid+1,r);
    update(now);
    return now;
}
int insert(int pre,int left_range,int right_range,int pos,int val){
    int now=++cnt;
    tree[now]=tree[pre];
    if(left_range==right_range){
        tree[now].val=val;
        return now;
    }
    int mid=left_range+right_range>>1;
    if(pos<=mid)tree[now].ls=insert(tree[pre].ls,left_range,mid,pos,val);
    else tree[now].rs=insert(tree[pre].rs,mid+1,right_range,pos,val);
    return now;
}
int query(int k,int left_range,int right_range,int pos){
    if(left_range==right_range)
        return tree[k].val;
    int mid=left_range+right_range>>1;
    if(pos<=mid)return query(tree[k].ls,left_range,mid,pos);
    else return query(tree[k].rs,mid+1,right_range,pos);
}
int main(){
    freopen("in.in","r",stdin);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&i[num]);
    rt[0]=Build(1,n);
    for(int i=1;i<=m;i++){
        int v,opt,loc,val;
        scanf("%d%d",&v,&opt);
        if(opt==1){
            scanf("%d%d",&loc,&val);
            rt[i]=insert(rt[v],1,n,loc,val);
        }
        else{
            scanf("%d",&loc);
            rt[i]=rt[v];
            printf("%d\n",query(rt[v],1,n,loc));
        }
    }
    return 0;
}