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

• Marvolo • 0条评论 •

可持久化数据结构,顾名思义,指的是一类可以支持回溯到某一历史版本并进行一系列相关操作的数据结构.通常以线段树为基础实现.典型的通过增加空间开销来提升效率的思想.我用空间换回超限的时间

常见的可持久化数据结构如可持久化线段树,可持久化并查集.丧心病狂一些的有可持久化平衡树(无旋Treap)等.

引入:可持久化数组

原理

考虑实现一种数据结构,支持下面三种操作:

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

每进行一次操作,都会得到一个新的历史版本.(对于第二种操作,可以视为得到了上一个历史版本的复制)

通常意义下的修改操作时间复杂度为O(1),如果需要实现可持久化的话,则还需要额外的O(n)的空间开销用于储存一个全新的数组.但这种原始的方式为空间带来了不可能承受的压力,而且时间复杂度也很爆炸.所以考虑对其进行优化.

注意到,每一次修改操作是只针对单点的,也就是说每次修改之后得到的全新版本和之前的版本至多有一处不同.朴素做法中每次O(n)的空间花费其实有很多是可以避免的.

为了充分利用历史版本的信息,考虑在需要维护的数组之上建一个线段树.这样,每次修改操作只会改变logn个节点所维护的信息.因此,每一次修改操作后,只新增维护了该位置的线段树节点.这样每次操作的空间消耗与时间消耗都变成了O(Logn).如下图示:

建树过程类似于普通线段树,但需要动态开点

inline int Build(int l,int r){
    int mid=(l+r)>>1,x=0;
    x=++tot;
    if (l==r)   {t[x].d=a[l];   return x;}
    t[x].l=Build(l,mid);    t[x].r=Build(mid+1,r);
    return x;
}

查询操作完全等同于普通线段树

inline int Query(int x,int l,int r,int p){
    int mid=(l+r)>>1;
    if (l==r)   return t[x].d;
    return (p<=mid)?Query(t[x].l,l,mid,p):Query(t[x].r,mid+1,r,p);
}

修改节点时,需要不断动态开点,更新节点的左儿子或右儿子

inline int Change(int pre,int l,int r,int p,int val){
    int x=0,mid=(l+r)>>1;
    x=++tot;    t[x]=t[pre];
    if (l==r)   {t[x].d=val;    return x;}
    (p<=mid)?t[x].l=Change(t[x].l,l,mid,p,val):t[x].r=Change(t[x].r,mid+1,r,p,val);
    return x;
}

注意该结构的空间消耗仍然很大,一般需要开16倍内存.

例题

洛谷3919

完整代码

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define N 1000010
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;

int n,m,tot,i,op,x,y,v,cnt;
int a[N],root[N];

struct Tree{
    int l,r,d;
}t[N*16];

inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &a,int &b){a^=b^=a^=b;}
inline int Min(int a,int b){return (a<b)?a:b;}
inline int Max(int a,int b){return (a>b)?a:b;}

inline int read(){
    int p=0,f=1;    char    c=getchar();
    while (c<48||c>57)  {if (c=='-')    f=-1;   c=getchar();}
    while (c>=48&&c<=57)    p=(p<<1)+(p<<3)+c-48,c=getchar();
    return p*f;
}

inline int Build(int l,int r){
    int mid=(l+r)>>1,x=0;
    x=++tot;
    if (l==r)   {t[x].d=a[l];   return x;}
    t[x].l=Build(l,mid);    t[x].r=Build(mid+1,r);
    return x;
}

inline int Change(int pre,int l,int r,int p,int val){
    int x=0,mid=(l+r)>>1;
    x=++tot;    t[x]=t[pre];
    if (l==r)   {t[x].d=val;    return x;}
    (p<=mid)?t[x].l=Change(t[x].l,l,mid,p,val):t[x].r=Change(t[x].r,mid+1,r,p,val);
    return x;
}

inline int Query(int x,int l,int r,int p){
    int mid=(l+r)>>1;
    if (l==r)   return t[x].d;
    return (p<=mid)?Query(t[x].l,l,mid,p):Query(t[x].r,mid+1,r,p);
}

int main(){
    n=read();   m=read();
    for (i=1;i<=n;i++)  a[i]=read();
    root[0]=Build(1,n);
    while (m--){
        v=read();   op=read();
        if (op==1){
            x=read();   y=read();
            root[++cnt]=Change(root[v],1,n,x,y);
        }   else {
            x=read();   root[++cnt]=root[v];
            printf("%d\n",Query(root[cnt],1,n,x));
        }
    }
    return 0;
}

可持久化线段树

原理

在可持久化数组的基础上,加上线段树的相关操作即可得到可持久化线段树.和前面的写法非常相像.注意这时节点上多了线段树所必须有的维护的区间左右端点.在建树的过程中设好即可.之后节点的复制的时候不需要做任何修改.其实也可以不储存相关信息,直接加到递归函数中也可以.

例题

COGS2554

代码

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define N 100010
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;

int n,m,i,op,x,y,v,tot,cnt;
int root[N],a[N];

struct Tree{
    int l,r,d,L,R;
}t[N*16];

inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &a,int &b){a^=b^=a^=b;}
inline int Min(int a,int b){return (a<b)?a:b;}
inline int Max(int a,int b){return (a>b)?a:b;}

inline int read(){
    int p=0,f=1;    char    c=getchar();
    while (c<48||c>57)  {if (c=='-')    f=-1;   c=getchar();}
    while (c>=48&&c<=57)    p=(p<<1)+(p<<3)+c-48,c=getchar();
    return p*f;
}

inline int Build(int l,int r){
    int mid=(l+r)>>1,x=++tot;
    t[x].L=l;   t[x].R=r;
    if (l==r)   {t[x].d=a[l];   return x;}
    t[x].l=Build(l,mid);    t[x].r=Build(mid+1,r);
    t[x].d=Max(t[t[x].l].d,t[t[x].r].d);
    return x;
}

inline int Query(int x,int l,int r){
    int mid=(t[x].L+t[x].R)>>1;
    if (t[x].L==l&&t[x].R==r)   return t[x].d;
    if (r<=mid) return Query(t[x].l,l,r);
    else if (l>mid) return Query(t[x].r,l,r);
    else return Max(Query(t[x].l,l,mid),Query(t[x].r,mid+1,r));
}

inline int Change(int pre,int p,int val){
    int x=++tot,mid=(t[pre].L+t[pre].R)>>1;
    t[x]=t[pre];
    if (t[x].L==t[x].R) {t[x].d=val;    return x;}
    (p<=mid)?t[x].l=Change(t[x].l,p,val):t[x].r=Change(t[x].r,p,val);
    t[x].d=Max(t[t[x].l].d,t[t[x].r].d);
    return x;
}

int main(){
    n=read();   m=read();
    for (i=1;i<=n;i++)  a[i]=read();
    root[1]=Build(1,n); cnt=1;
    while (m--){
        op=read();  v=read();   x=read();   y=read();
        (op==0)?printf("%d\n",Query(root[v],x,y)):root[++cnt]=Change(root[v],x,y);
    }
    return 0;
}

可持久化并查集

原理

同理,还是使用线段树维护数组.这时数组中储存的内容变成了父节点储存的信息.朴素的并查集做法效率比较低,一般实现的时候都是按秩合并的并查集.下面的版本是不带路径压缩的,如果需要可以加上.

和普通并查集类似,查询第v个版本中的节点祖先:

inline int Find(int v,int x){
    int p=Query(v,1,n,x);
    return (t[p].d==x)?p:Find(v,t[p].d);
}

注意查询结果返回的不是直接的祖先信息,而是节点的标号.之所以这样处理是为了之后方便进行按秩合并.

进行连接操作时,直接在对应版本里修改即可:

inline int Change(int pre,int l,int r,int p,int val){
    int x=++tot,mid=(l+r)>>1;
    t[x]=t[pre];
    if (l==r)   {t[x].d=val;    return x;}
    (p<=mid)?t[x].l=Change(t[x].l,l,mid,p,val):t[x].r=Change(t[x].r,mid+1,r,p,val);
    return x;
}

因为是按秩合并,所以有增加秩的过程:

inline void Add(int x,int l,int r,int p){
    int mid=(l+r)>>1;
    if (l==r)   {t[x].dep++;    return;}
    (p<=mid)?Add(t[x].l,l,mid,p):Add(t[x].r,mid+1,r,p);
}

进行查询和连接操作时的详细过程如下:

            root[i]=root[i-1];  y=read();
            fx=Find(root[i],x); fy=Find(root[i],y);
            if (t[fx].d==t[fy].d)   continue;
            if (t[fx].dep>t[fy].dep)    Swap(fx,fy);
            root[i]=Change(root[i],1,n,t[fx].d,t[fy].d);
            if (t[fx].dep==t[fy].dep)   Add(root[i],1,n,t[fy].d);

首先进行查询操作,然后按秩合并,并修改相关的祖先值.最后维护一下秩.和普通的并查集完全相同的流程.

例题

洛谷3402

代码

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define N 200010
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;

int n,m,i,x,y,tot,op,fx,fy;
int root[N];

struct Tree{
    int l,r,d,dep;
}t[N*16];

inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &a,int &b){a^=b^=a^=b;}
inline int Min(int a,int b){return (a<b)?a:b;}
inline int Max(int a,int b){return (a>b)?a:b;}

inline int read(){
    int p=0;    char    c=getchar();
    while (c<48||c>57)  c=getchar();
    while (c>=48&&c<=57)    p=(p<<1)+(p<<3)+c-48,c=getchar();
    return p;
}

inline int Build(int l,int r){
    int x=++tot,mid=(l+r)>>1;
    if (l==r)   {t[x].d=l;  return x;}
    t[x].l=Build(l,mid);    t[x].r=Build(mid+1,r);
    return x;
}

inline int Query(int x,int l,int r,int p){
    int mid=(l+r)>>1;
    if (l==r)   return x;
    return (p<=mid)?Query(t[x].l,l,mid,p):Query(t[x].r,mid+1,r,p);
}

inline int Find(int v,int x){
    int p=Query(v,1,n,x);
    return (t[p].d==x)?p:Find(v,t[p].d);
}

inline int Change(int pre,int l,int r,int p,int val){
    int x=++tot,mid=(l+r)>>1;
    t[x]=t[pre];
    if (l==r)   {t[x].d=val;    return x;}
    (p<=mid)?t[x].l=Change(t[x].l,l,mid,p,val):t[x].r=Change(t[x].r,mid+1,r,p,val);
    return x;
}

inline void Add(int x,int l,int r,int p){
    int mid=(l+r)>>1;
    if (l==r)   {t[x].dep++;    return;}
    (p<=mid)?Add(t[x].l,l,mid,p):Add(t[x].r,mid+1,r,p);
}

int main(){
    n=read();   m=read();
    root[0]=Build(1,n);
    for (i=1;i<=m;i++){
        op=read();  x=read();
        if (op==1){
            root[i]=root[i-1];  y=read();
            fx=Find(root[i],x); fy=Find(root[i],y);
            if (t[fx].d==t[fy].d)   continue;
            if (t[fx].dep>t[fy].dep)    Swap(fx,fy);
            root[i]=Change(root[i],1,n,t[fx].d,t[fy].d);
            if (t[fx].dep==t[fy].dep)   Add(root[i],1,n,t[fy].d);
        }   else if (op==2) root[i]=root[x];
            else {
                root[i]=root[i-1];  y=read();
                fx=Find(root[i],x); fy=Find(root[i],y);
                printf("%d\n",(t[fx].d==t[fy].d)?1:0);
        }
    }
    return 0;
}
声明: 本文采用 BY-NC-SA 协议进行授权，如无注明均为原创，转载请注明转自 Marvolo
本文地址: 可持久化数据结构学习笔记
可持久化 学习笔记
说点什么
登录
支持Markdown语法
好耶,沙发还空着ヾ(≧▽≦*)o
Loading...