欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

[模板] 可持久化数组

程序员文章站 2024-03-04 12:26:35
...

传送门

可持久化线段树

建树、单点修改、单点查询

#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN (1000005*20)

int root[MAXN];

inline int read() {
    int flag = 1,num = 0; char ch = getchar();
    while(ch>'9'||ch<'0') {
        if(ch=='-') flag = -1;
        ch = getchar();
    }
    while(ch>='0'&&ch<='9') {
        num = num*10 + ch - 48;
        ch = getchar();
    }
    return num*flag;
}

class Persistent_Segment_Tree {
    
    private:
        int lson[MAXN],rson[MAXN],val[MAXN],cnt;
    public:
        void Build(int& rt,int l,int r) {
            rt = ++cnt;
            if(l==r) {
                val[rt] = read();
                return;
            }
            int mid = (l+r) >> 1;
            Build(lson[rt],l,mid); Build(rson[rt],mid+1,r);
        }
        void update(int& rt,int pre,int l,int r,int x,int value) {
            rt = ++cnt; val[rt] = val[pre];
            lson[rt] = lson[pre]; rson[rt] = rson[pre];
            if(l==r) {
                val[rt] = value;
                return;
            }
            int mid = (l+r)>>1;
            if(x<=mid) update(lson[rt],lson[pre],l,mid,x,value);
            else update(rson[rt],rson[pre],mid+1,r,x,value);
        }
        int query(int rt,int l,int r,int x) {
            if(l==r) return val[rt];
            int mid = (l+r) >> 1;
            if(x<=mid) return query(lson[rt],l,mid,x);
            else return query(rson[rt],mid+1,r,x);
        }
}T;

int N,M;

int main() {

    N = read(); M = read();
    T.Build(root[0],1,N);

    int pre,opt,x,value;
    for(int i=1;i<=M;++i) {
        scanf("%d%d",&pre,&opt);
        if(opt==1) {
            scanf("%d%d",&x,&value);
            T.update(root[i],root[pre],1,N,x,value);
        }
        else {
            scanf("%d",&x);
            printf("%d\n",T.query(root[pre],1,N,x));
            root[i] = root[pre];
        }
    }

    return 0;
}