可持久化数组¶

如题，你需要维护这样的一个长度为 \(N\) 的数组，支持如下几种操作

对于操作1，格式为\(v_i \ 1 \ p_i \ {value}_i\)，即为在版本\(v_i\)的基础上，将 \(a_{p_i}\) 修改为 \({value}_i\)。
对于操作2，格式为\(v_i \ 2 \ p_i\)，即访问版本\(v_i\)中的 \(a_{p_i}\)的值，注意：生成一样版本的对象应为 \(v_i\)。

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

代码¶

还是很简单的。

/*////////ACACACACACACAC///////////
       . Coding by Ntsc .
       . FancyKnowledge .
       . Prove Yourself .
/*////////ACACACACACACAC///////////

//
#include<bits/stdc++.h>

//
#define int long long
#define ull unsigned long long
#define db double
#define endl '\n'
#define err(fmt, ...) fprintf(stderr, "[%d] : " fmt "\n", __LINE__, ##__VA_ARGS__)
///*
#define pr pair<double,int>
#define pf first
#define ps second
#define pb push_back
//*/

//
using namespace std;
//
const int N=1e6+5;
const int M=1e3;
int MOD=1e9+7;
const int MMOD=903250223;
const int INF=1e9;
const int IINF=1e18;
const db eps=1e-9;
//
int n,m,a[N],b,q,sw,k,ans,res,tmp,cnt,mul[N];
int  rt[N];
int vcnt;//版本计数
int L;

struct node{
    int lc,rc,v;
}tr[N<<5];//16倍空间

void pushup(int x){
    //
}

void build(int &x,int l,int r){
    x=++cnt;
    if(l==r){
        tr[x].v=a[l];
        return ;
    }
    int mid=l+r>>1;
    build(tr[x].lc,l,mid);
    build(tr[x].rc,mid+1,r);
}

void insert(int pre,int &now,int l,int r,int p,int v){
    now=++cnt;//建立新节点
    if(l==r){
        tr[now].v=v;
        return ;
    }
    int mid=l+r>>1;
//  tr[now]=tr[pre];
//  tr[now].v=tr[pre].v;//更新,因为如下
    if(p<=mid){
        tr[now].rc=tr[pre].rc;//也可以在一开始复制旧的点的信息
        insert(tr[pre].lc,tr[now].lc,l,mid,p,v);
    }
    else {
        tr[now].lc=tr[pre].lc;
        insert(tr[pre].rc,tr[now].rc,mid+1,r,p,v);
    }

//  pushup(now);
}

int query(int x,int l,int r,int p){
    if(l==r)return tr[x].v;

    int mid=l+r>>1;
    if(p<=mid)return query(tr[x].lc,l,mid,p);
    return query(tr[x].rc,mid+1,r,p);
}

signed main(){

//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
//  freopen(".txt","w",stderr);

    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++){
//      cin>>a[i];
        scanf("%lld",&a[i]);
    }

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

    while(m--){
        int v,op,loc,val;
//      cin>>v>>op>>loc;
        scanf("%lld%lld%lld",&v,&op,&loc);
        if(op==1){
            scanf("%lld",&val);
            insert(rt[v],rt[++vcnt],1,n,loc,val);
//          cerr<<"rt"<<vcnt<<"]="<<tr[rt[vcnt]].rc<<endl;
        }else{
            cout<<query(rt[v],1,n,loc)<<endl;
            rt[++vcnt]=rt[v];
        }
    }

    return 0;
}

//check your long long and the size of memery!!!

树上版可持久化线段树求k小（树上主席树）¶

www.luogu.com.cn

模型

求树上从x-y路径上的地k小值

做法

我们考虑进行树上差分。我们对每一个节点x维护一个权值线段树t_x，代表着从x到根节点的路径上的数值发布情况。

对于树的构建，我们这样：在x的父亲的版本基础上加入x，就形成了x版本的线段树。

对于查询，我们工具树上差分得出代表链x-y的树应该是\(t_x+t_y-t_{lca}-t_{fa(lca)}\)，于是我们4个指针分别指向即可。

时刻记住，主席树的功能是让你快速求出特定区间内某值域范围的数字个数，方便二分，而不是直接记录答案！