可持久化数据结构学习笔记

前言

这篇文章详细地介绍了 OI 竞赛常用的可持久化数据结构，部分图片尺寸过大，建议单击图片放大观看。转载此文章的任何部分均需注明出处。

文章目录

前言 1 可持久化线段树1.1 问题引入1.2 权值线段树1.3 可持久化线段树1.4 例题 2 可持久化数组2.1 问题引入2.2 问题解决2.3 参考代码 3 支持修改的可持久化线段树3.1 问题引入3.2 问题解决3.3 参考代码 4 可持久化并查集4.1 问题引入4.2 问题解决4.3 参考代码

1 可持久化线段树

1.1 问题引入

您需要写一个数据结构，维护一个数列 $a[1...N]$，支持以下操作： 输入 l r k（$l\le r,k\le r-l+1$），求 $a[l...r]$ 中第 $k$ 小的数。

这就是经典的 “静态区间第 k 小” 问题。

可持久化线段树（Persistent Segment Tree）可以很好地解决这个问题。在学习可持久化线段树时，我们首先要了解权值线段树。

1.2 权值线段树

权值线段树是一种维护值而非下标的线段树，为了方便理解，有时也被称作 “值域线段树”。

设 $x$ 是一权值线段树上的一个点，它维护的区间是 $[x.l,x.r]$，数据是 $x.d$，则它表示的意思是：原数组中，值在区间 $[x.l,x.r]$ 内的数一共有 $x.d$ 个。

举个例子。有一个数组 $a[]=\{1,5,3,8\}$，则它的权值线段树是 权值线段树可以解决整个区间的查询问题。换句话说，当 $l=1,r=N$ 时，我们就可以用权值线段树求解了。

那如果 $l\ne 1$ 或 $r\ne N$，我们又该怎么办呢？

一种很显然的想法就是，我建 $\frac{N(N+1)}{2}$ 棵权值线段树，也就是说，$\forall 1\le l\le r\le N$，我都建一棵权值线段树维护 $a[l...r]$。这样做的话空间复杂度是 $T(N^3)$，不能接受。而且这样做的话，光是建树就会导致超时。

不难发现，权值线段树是可加减的。也就是说，我可以只开 $N$ 棵权值线段树，第 $i$ 棵维护 $a[1...i]$ 范围的数（这里用了前缀和思想）。如果查询 $[l,r]$ 区间，就用第 $r$ 棵树减去第 $l-1$ 棵树即可。 时间复杂度 $O(N^2+M\log N)$，空间复杂度 $T(N^2)$，仍然不够优秀。

1.3 可持久化线段树

观察上面的四棵树。不难发现，第 $i$ 棵树与第 $i-1$ 棵树只有一条链不一样，其余部分完全相同。那么，我们能不能在这里做点文章，压缩时间、空间复杂度呢？

答案是肯定的。我们每次建树时，不需要新建一棵完整的树，只需要在原来的树上加一条链就行了。

还是以 $a[]=\{1,5,3,8\}$ 为例，画出可持久化线段树： 最后一棵就是最终形态的可持久化线段树了。时间复杂度 $O(N\log N)$，空间复杂度 $T(N\log N)$。

至此，可持久化线段树的基本内容已经讲解完毕了，我们现在已经可以解决文首提出的问题了。

1.4 例题

静态区间第 k 小问题 如题，给定 $N$ 个整数构成的序列，将对于指定的闭区间查询其区间内的第 $K$ 小值。

解 将两棵可持久化线段树相减（容易想到，如果将第 $r$ 棵树减去第 $l-1$ 棵树，那结果就是 $[l,r]$ 区间的权值线段树了）。从根节点开始，往下遍历，若左子树维护区间的数的个数 $d<K$，则走向左儿子，否则走向右儿子；重复以上操作，直到走到叶子节点，该节点的下标即为答案。

参考代码

#include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; const int MAXN=200010; int n,m; struct index{ int x,y; friend bool operator<(const index a,const index b){ return a.y<b.y; } }a[MAXN]; int b[MAXN]; int mp[MAXN]; int sx,sy,sd; inline int read(){ int x=0; char c; do c=getchar(); while(c<'0'||c>'9'); while(c>='0'&&c<='9') x=x*10+c-48,c=getchar(); return x; } struct PreSegTree{ struct index{ int l,r,ls,rs,d; index(){ l=r=ls=rs=d=0; } }e[MAXN*40]; int len; int root[MAXN]; PreSegTree(){ len=0;root[0]=1; } void buildtree(int l,int r){ int me=++len; e[me].l=l;e[me].r=r; if(l==r) return; int mid=(l+r)/2; e[me].ls=len+1;buildtree(l,mid); e[me].rs=len+1;buildtree(mid+1,r); } void grow(int rt,int x){ int l=e[rt].l,r=e[rt].r,me=++len; e[me].l=l;e[me].r=r; if(l==r){ e[me].d=e[rt].d+1; return; } int mid=(l+r)/2; if(x<=mid){ e[me].ls=len+1;e[me].rs=e[rt].rs; grow(e[rt].ls,x); }else{ e[me].ls=e[rt].ls;e[me].rs=len+1; grow(e[rt].rs,x); } e[me].d=e[e[me].ls].d+e[e[me].rs].d; } void insert(int x,int d){ root[x]=len+1; grow(root[x-1],d); } int query(int rootl,int rootr,int k){ int LS=e[rootl].ls,RS=e[rootr].ls; int D=e[RS].d-e[LS].d; if(e[rootl].l==e[rootl].r) return e[rootl].r; if(k<=D) return query(LS,RS,k); else return query(e[rootl].rs,e[rootr].rs,k-D); } }T; int main(){ n=read();m=read(); T.buildtree(1,n); for(int i=1;i<=n;++i) a[i].x=i,a[i].y=read(); sort(a+1,a+n+1); int tmp=0,last=-0x3f3f3f3f; for(int i=1;i<=n;++i){ if(a[i].y!=last){ ++tmp; mp[tmp]=a[i].y; } b[a[i].x]=tmp; last=a[i].y; } for(int i=1;i<=n;++i) T.insert(i,b[i]); for(int i=1;i<=m;++i){ sx=read();sy=read();sd=read(); printf("%d\n",mp[T.query(T.root[sx-1],T.root[sy],sd)]); } }

2 可持久化数组

2.1 问题引入

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

在某个历史版本上修改某一个位置上的值；访问某个历史版本上的某一位置的值。

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

2.2 问题解决

算法 1 我们可以考虑对每一个版本开一个数组，这就是最暴力的打法了。

算法 2 高级一点，我们可以考虑对每一个版本建一棵线段树，查询时在线段树上查询，这样的效率还不如一个暴力数组。

算法 3 考虑用可持久化线段树维护每个位置上的值，也就是说每修改一次就加一条链。查询操作与上文类似，在此不再赘述。

时间复杂度 $O((N+M)\log N)$，空间复杂度 $T(N+M\log N)$。

2.3 参考代码

#include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; const int MAXN=1000010; int n,m; int sx,sy,sc,sd; int b[MAXN]; inline int read(){ int x=0,f=0; char c; do {c=getchar(); if(c=='-') f=1;} while(c<'0'||c>'9'); while(c>='0'&&c<='9') x=x*10+c-48,c=getchar(); return f?-x:x; } struct PreSegTree{ struct index{ int l,r,ls,rs,d; index(){ l=r=ls=rs=d=0; } }e[MAXN*25]; int len; int root[MAXN]; PreSegTree(){ len=0;root[0]=1; } void buildtree(int l,int r){ int me=++len; e[me].l=l;e[me].r=r; if(l==r){ e[me].d=b[l]; return; } int mid=(l+r)/2; e[me].ls=len+1;buildtree(l,mid); e[me].rs=len+1;buildtree(mid+1,r); } void grow(int rt,int x,int d){ int l=e[rt].l,r=e[rt].r,me=++len; e[me].l=l;e[me].r=r; if(l==r){ if(d==-1) e[me].d=e[rt].d; else e[me].d=d; return; } int mid=e[e[rt].ls].r; if(x<=mid){ e[me].ls=len+1;e[me].rs=e[rt].rs; grow(e[rt].ls,x,d); }else{ e[me].ls=e[rt].ls;e[me].rs=len+1; grow(e[rt].rs,x,d); } } void insert(int num,int rt,int x,int d){ root[num]=len+1; grow(root[rt],x,d); } int query(int root,int x){ if(e[root].l==e[root].r) return e[root].d; int ls=e[root].ls,rs=e[root].rs; int mid=e[ls].r; if(x<=mid) return query(ls,x); else return query(rs,x); } }T; int main(){ n=read();m=read(); for(int i=1;i<=n;++i) b[i]=read(); T.buildtree(1,n); for(int i=1;i<=m;++i){ sx=read();sy=read();sc=read(); if(sy==1){ sd=read(); T.insert(i,sx,sc,sd); }else{ printf("%d\n",T.query(T.root[sx],sc)); T.insert(i,sx,sc,-1); } } }

3 支持修改的可持久化线段树

3.1 问题引入

我们不妨把 1.1 节提出的问题强化一下。

Dynamic Rankings （动态区间第 k 小问题）您需要写一个数据结构，维护一个数列 $a[1...N]$，支持以下操作：

1 x k （$1\le x\le N$），将 $a[x]$ 的值设为 $k$；2 l r k（$l\le r,k\le r-l+1$），求 $a[l...r]$ 中第 $k$ 小的数。

如果修改可持久化线段树，单次操作的时间复杂度变成 $O(N\log N)$，这显然不是我们希望看到的。

那么问题来了，我们怎样才能让可持久化线段树支持修改呢？

3.2 问题解决

再看一次我们建的 $N$ 棵权值线段树。 不难想到，修改第 $i$ 棵树的的点时，需要同时修改第 $i+1,i+2,...,N$ 棵权值线段树。

考虑一下什么数据结构可以加速这种区间修改过程，不难想到树状数组，尝试用树状数组维护这 $N$ 棵权值线段树： 请注意：权值线段树内的点的数据以树状数组的实际情况为准！

这样我们就能使用差分思想实现区间修改了。时间复杂度 $O(N{\log }^{2}N)$，空间复杂度 $T(N^2)$。使用动态开点优化空间复杂度后，复杂度降为 $T(N{\log }^{2}N)$。

3.3 参考代码

#include<cstdio> #include<cstdlib> #include<cstring> #include<map> #include<algorithm> using namespace std; const int MAXN=200010; int n,m,N; char str[10]; int sx[MAXN],sy[MAXN],sd[MAXN]; int a[MAXN],s[MAXN]; int bk[MAXN]; int to[MAXN]; map<int,int> mp; inline int read(){ int x=0; char c; do c=getchar(); while(c<'0'||c>'9'); while(c>='0'&&c<='9') x=x*10+c-48,c=getchar(); return x; } int lowbit(int x){ return x&(-x); } struct Treearray{ struct Index{ int l,r,d; Index *ls,*rs; Index(){ l=r=d=0;ls=rs=NULL; } }; Index *root[MAXN],*me1[MAXN],*me2[MAXN]; int len1,len2; //权值线段树类 struct Segtree{ //新建一条链 void insert(Index*me,int x,int d){ //到达叶子节点，结束 if((x==me->l)&&(x==me->r)){ me->d+=d; return; } const int mid=(me->l+me->r)/2; if(x<=mid){ //目标节点在左子树内 //没有左儿子，新建节点 if(NULL==me->ls){ me->ls=new Index(); me->ls->l=me->l;me->ls->r=mid; } insert(me->ls,x,d); }else{ if(NULL==me->rs){ me->rs=new Index(); me->rs->l=mid+1;me->rs->r=me->r; } insert(me->rs,x,d); } //更新自己的数据 me->d=0; if(NULL!=me->ls) me->d+=(me->ls->d); if(NULL!=me->rs) me->d+=(me->rs->d); } }T[MAXN]; //建立树状数组，初始化每棵线段树 void init(){ for(int i=1;i<=n;++i){ root[i]=new Index(); root[i]->l=1;root[i]->r=N; } } //将a[x]的值设为d void change(int x,int d){ //在树状数组中找到所有管理x位置的点，把它们insert一遍 for(int i=x;i<=n;i+=lowbit(i)){ if(a[x]) T[i].insert(root[i],a[x],-1); T[i].insert(root[i],d,1); } a[x]=d; } //返回每棵树上的当前位置的左子树的数据之和 int sum(){ int cnt=0; for(int i=1;i<=len2;++i) if(me2[i]!=NULL&&me2[i]->ls!=NULL) cnt+=me2[i]->ls->d; for(int i=1;i<=len1;++i) if(me1[i]!=NULL&&me1[i]->ls!=NULL) cnt-=me1[i]->ls->d; return cnt; } //查询a[l...r]中第k小的数 int query(int l,int r,int k){ //求出左子树数据之和，与k比较 int d=sum(),mid=(l+r)/2; //到达叶子节点，结束 if(l==r) return l; if(k<=d){//进入左子树 for(int i=1;i<=len1;++i) if(me1[i]!=NULL) me1[i]=me1[i]->ls; for(int i=1;i<=len2;++i) if(me2[i]!=NULL) me2[i]=me2[i]->ls; return query(l,mid,k); }else{//进入右子树 for(int i=1;i<=len1;++i) if(me1[i]!=NULL) me1[i]=me1[i]->rs; for(int i=1;i<=len2;++i) if(me2[i]!=NULL) me2[i]=me2[i]->rs; return query(mid+1,r,k-d); } } //初始化后调用query函数 int work(int l,int r,int k){ len1=len2=0; for(int i=r;i>0;i-=lowbit(i)) me2[++len2]=root[i]; for(int i=l-1;i>0;i-=lowbit(i)) me1[++len1]=root[i]; return query(1,N,k); } }T; int main(){ memset(a,0,sizeof(a)); memset(sd,-1,sizeof(sd)); n=read();m=read(); for(int i=1;i<=n;++i) s[i]=read(); for(int i=1;i<=m;++i){ scanf("%s",str);sx[i]=read();sy[i]=read(); if('C'!=str[0]) sd[i]=read(); } int blen=0,now=0,last=-1; for(int i=1;i<=n;++i) bk[++blen]=s[i]; for(int i=1;i<=m;++i) if(-1==sd[i]) bk[++blen]=sy[i]; sort(bk+1,bk+blen+1); for(int i=1;i<=blen;++i){ if(bk[i]!=last){ ++now; last=bk[i]; } mp[bk[i]]=now;to[now]=bk[i]; } N=now; T.init(); for(int i=1;i<=n;++i) T.change(i,mp[s[i]]); for(int i=1;i<=m;++i) if(-1==sd[i]) T.change(sx[i],mp[sy[i]]); else printf("%d\n",to[T.work(sx[i],sy[i],sd[i])]); }

4 可持久化并查集

4.1 问题引入

（luogu P3402 【模板】可持久化并查集）你有 $n$ 个集合，现在有 $m$ 个操作：

1 a b 合并 a,b 所在集合2 k 回到第 k 次操作之后的状态(查询算作操作)3 a b 询问 a,b 是否属于同一集合，是则输出1否则输出0

4.2 问题解决

这道题中不能使用路径压缩节约时间，因为修改祖宗的 fa[] 的时间复杂度是不可接受的。

那我们就只能打一个 $O(N^2)$ 的并查集了吗？不不不，设计数组 $deep[i]$ 表示 $i$ 所在集合的大小，每次将小的集合的父亲设置为大的集合（按秩合并），就能保证并查集时间复杂度是 $O(N\alpha (N))$，总的时间复杂度是 $O(N\log N\alpha (N))$。

4.3 参考代码