1.可持久化数组

这个是众多可持久化数据结构的基础，实现方式也是最基础的，只需要用到主席树即可

需要维护这样的一个长度为n的数组，支持如下几种操作

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

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

我们发现更新线段树的时候，每层仅仅修改了一个点，所以我们记录新的版本不需要把整棵树复制一遍，而是只需要把更新的节点新建出来即可 

【代码】

int build(int now,int l,int r)
{now=++cnt;if(l==r){tr[now].val=a[l];return cnt;}int mid=(l+r)>>1;tr[now].l=build(tr[now].l,l,mid);tr[now].r=build(tr[now].r,mid+1,r);return now;
}
int update(int now,int l,int r,int x,int val)
{cnt++; tr[cnt]=tr[now]; now=cnt;if(l==r){tr[now].val=val;return now;}int mid=(l+r)>>1;if(x<=mid) tr[now].l=update(tr[now].l,l,mid,x,val);else tr[now].r=update(tr[now].r,mid+1,r,x,val);return now;
}
int query(int now,int l,int r,int x)
{if(l==r) return tr[now].val;int mid=(l+r)>>1;if(x<=mid) return query(tr[now].l,l,mid,x);else return query(tr[now].r,mid+1,r,x);
}
int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) scanf("%d",&a[i]);root[0]=build(0,1,n);int x,y,z,op;for(int i=1;i<=m;i++){scanf("%d%d",&x,&op);if(op==1){scanf("%d%d",&y,&z);root[i]=update(root[x],1,n,y,z);}else{scanf("%d",&y);printf("%d\n",query(root[x],1,n,y));root[i]=root[x];}}return 0;
}

2.可持久化并查集

我们要想维护历史版本的fa数组，自然会想到可持久化数组（利用主席树实现），这里的并查集就不能使用路径压缩了，只能使用按秩合并来保证复杂度

【代码】

int build(int now,int l,int r)
{now=++cnt;if(l==r){f[now]=l;return now;}int mid=(l+r)>>1;tr[now].l=build(tr[now].l,l,mid);tr[now].r=build(tr[now].r,mid+1,r);return now;
}
void update(int &now ,int pre,int l,int r,int x,int val)
{now=++cnt;if(l==r){f[now]=val;dep[now]=dep[pre];return;}tr[now].l=tr[pre].l;tr[now].r=tr[pre].r;int mid=(l+r)>>1;if(x<=mid) update(tr[now].l,tr[pre].l,l,mid,x,val);else update(tr[now].r,tr[pre].r,mid+1,r,x,val);
}
int query(int now,int l,int r, int x)
{if(l==r) return now;int mid=(l+r)>>1;if(x<=mid) return query(tr[now].l,l,mid,x);else return query(tr[now].r,mid+1,r,x);
}
int find(int now,int x)
{int father=query(now,1,n,x);if(x==f[father]) return father;return find(now,f[father]);
}
void add(int now,int l,int r,int x) //使得now中每个点的深度+1
{if(l==r){dep[now]++;return;}int mid=(l+r)>>1;if(x<=mid) add(tr[now].l,l,mid,x);else add(tr[now].r,mid+1,r,x);
}
int main()
{// freopen("a.in","r",stdin);//  freopen("a.out","w",stdout);int op,x,y;scanf("%d%d",&n,&m);root[0]=build(0,1,n);for(int i=1;i<=m;i++){scanf("%d",&op);if(op==1){scanf("%d%d",&x,&y);root[i]=root[i-1];int f1=find(root[i],x),f2=find(root[i],y);if(f[f1]==f[f2]) continue;if(dep[f1]>dep[f2]) swap(f1,f2);update(root[i],root[i-1],1,n,f[f1],f[f2]);if(dep[f1]==dep[f2]) add(root[i],1,n,f[f2]);}if(op==2){scanf("%d",&x);root[i]=root[x];}if(op==3){root[i]=root[i-1];scanf("%d%d",&x,&y);int f1=find(root[i],x),f2=find(root[i],y);if(f[f1]==f[f2]) printf("1\n");else printf("0\n");}}return 0;
}

【应用】