可持久化数据结构(三)

摘要

本文介绍了可持久化块状链表和可持久化平衡树。

块状链表的持久化

首先讲一下这玩意儿,它就是 个用链表连起的数组。

相邻两个块大小之和大于等于 ,单个块大小小于等于 .

插入 / 删除元素

找到所在的块 ,插入 / 删除元素 ,总复杂度 .

维护

每次操作完了,检查块与相邻块的大小,如果大了就分割,小了就合并。

因此总的复杂度仍是

但说实话这玩意儿没什么鸟用 emmm

持久化

每次操作,我们直接建立一个新的块。在维护的时侯,如果要合并就合并到新的块,要分割就分成两个新的块。

可持久化平衡树

顾名思义,可以维护平衡树的历史版本信息,给一道象征性的例题

在某一历史版本的序列上插入 / 删除一个数,查询一个数的排名 / 前驱 / 后继,查询第 k 小的数

对于带旋转的一类平衡树而言,他们的父子关系是会变化的,因此无法持久化。不带旋转的则是 FHQ Treap,本文介绍的就是 FHQ Treap 的持久化

背景

这里给出一些背景函数和变量,不知道含义的参见我写的 FHQ Treap

#include<cstdio>
using namespace std;
const int N=5e5+5,SZ=1<<24;
int n;

int seed=1,tot;// 总结点数
int lc[SZ],rc[SZ],val[SZ],rnd[SZ],sz[SZ];
int rt[SZ];

函数

int rrand(){return seed*=482711;}
int new_node(int v){// 新建一个权值为 v 的结点
    ++tot, lc[tot]=rc[tot]=0;
    sz[tot]=1, val[tot]=v, rnd[tot]=rrand();
    return tot;
}
int cp_node(int u){// 从结点 u 复制一个新的结点
    ++tot, lc[tot]=lc[u], rc[tot]=rc[u];
    sz[tot]=sz[u], val[tot]=val[u], rnd[tot]=rnd[u];
    return tot;
}
void pushup(int u){// 向上更新信息
    sz[u]=sz[lc[u]]+sz[rc[u]]+1;
}

Split

分割操作,需要新建两个结点 x,y 保存新的两个平衡树。注意到我们的 split 的过程与线段树的过程是相似的,都是从上往下处理,因此新建结点的方式也是相似的

void split(int u,int k,int &x,int &y){// 可持久化分割,xy 为新建结点
    if(!u){x=y=0;return;}
    int u2=cp_node(u);// 副本结点
    if(val[u]<=k)x=u2, split(rc[u2],k,rc[u2],y);
    else y=u2, split(lc[u2],k,x,lc[u2]);
    pushup(u2);
}

Merge

Merge 的实现其实是不唯一的,这就要看你是否将原来 split 出来的若干个子平衡树当作一个版本。如果当作一个版本,那么 Merge 同样需要新建结点;如果不当做独立的版本,那么直接修改即可。大多数时侯我们是不会把 split 出来的子平衡树森林当作单独的历史版本的,接下来给出的就是不当作版本的 Merge

int merge(int x,int y){// 和原 FHQ Treap 的 merge 一样
    if(!x||!y)return x+y;
    if(rnd[x]<rnd[y])return rc[x]=merge(rc[x],y), pushup(x), x;
    else return lc[y]=merge(x,lc[y]), pushup(y), y;
}

平衡树操作

各个函数的意义可以参见我写的 FHQ Treap。这里仅仅是把参数列表加了一个 u 表示所基于的版本编号。其余操作基本不变

int insert(int v,int u){// 插入键值,返回新的树根
    int x,y;
    split(u,v-1,x,y);
    int z=new_node(v);
    return merge(x,merge(z,y));
}
int del(int v,int u){
    int x,y,z;
    split(u,v-1,x,y), split(y,v,y,z);
    if(y)y=merge(lc[y],rc[y]);
    return merge(x,merge(y,z));
}
int rank(int v,int u){// 这里虽然新建了 x,y 的结点,但是不需要这个版本,舍弃
    int x,y;
    split(u,v-1,x,y);
    return sz[x]+1;
}
int kth(int k,int u){// 第 k 小的数
    while(sz[lc[u]]+1!=k){if(k<=sz[lc[u]])u=lc[u];
        else k-=sz[lc[u]]+1,u=rc[u];
    }
    return val[u];
}
int pre(int v,int u){int rk=rank(v,u);
    if(rk==1)return -2147483647;//v 是第一,没有前驱
    else return kth(rk-1,u);
}
int suc(int v,int u){int rk=rank(v+1,u);
    if(rk>sz[u])return 2147483647;
    return kth(rk,u);
}

主函数

由于上述代码节选自我 Luogu3835 的提交代码,故给出主函数的部分

int main(){scanf("%d",&n);
    for(int i=1;i<=n;i++){
        int v,op,x;
        scanf("%d%d%d",&v,&op,&x);
        //printf("(%d,%d,%d)\n",v,op,x);
        if(op==1){rt[i]=insert(x,rt[v]);
        }else if(op==2){rt[i]=del(x,rt[v]);
        }else if(op==3){printf("%d\n",rank(x,rt[v])), rt[i]=rt[v];
        }else if(op==4){printf("%d\n",kth(x,rt[v])), rt[i]=rt[v];
        }else if(op==5){printf("%d\n",pre(x,rt[v])), rt[i]=rt[v];
        }else {printf("%d\n",suc(x,rt[v])), rt[i]=rt[v];
        }
    }
    return 0;
}

把上面的代码连起来即为完整代码


 上一篇
FHQ Treap 入门 FHQ Treap 入门
2019.9.19 编入精选文章。 摘要 整整四个月的沉寂,四个月的恐惧自闭,就在最后的 6 个小时,在凌晨 12 点 48 分,他醒了!扼住了平衡树的咽喉 emmm(手动滑稽) FHQ Treap | Treap | Splay大概讲一
2019.05.18
下一篇 
就《菊与刀》浅谈二战时期日本国民的性格 就《菊与刀》浅谈二战时期日本国民的性格
摘要 语文作业之读书报告…… I 前言谈到日本,想必每个人都有截然不同的看法。我知道我在本文所提到的观点必然是有人反对的。不过也并非不可,毕竟它正是如此矛盾。 我们知道在二战时期,日本法西斯发动了以侵华为主的战争。而这个时期国民党与共产党
2019.05.11
  目录