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

可持久化数据结构

What:一种可以保留历史版本的数据结构。

一个具有持久化能力的数据结构在其被修改后可以保存当前的状态,从本质上来说,这样的数据结构是不可改变类型

可持久化数据结构(Persistent data structure)就是利用函数式编程的思想使其支持询问历史版本、同时充分利用它们之间的共同数据来减少时间和空间消耗。

包括可持久化线段树,可持久化字典树,可持久化平衡树,可持久化链表,
可持久化并查集等

可持久化线段树

可持久化线段树又称主席树,函数式线段树。

主席树就是利用函数式编程的思想来使线段树支持询问历史版本、同时充分利用它们之间的共同数据来减少时间和空间消耗的增强版的线段树。
很多问题如果用线段树处理的话需要采用离线思想,若用主席树则可直接在线处理。故很多时候离线线段树求解可以转化为在线主席树求解。注意,主席树本质就是线段树,变化就在其实现可持久化,后一刻可以参考前一刻的副本,二者共同部分很多。一颗线段树的节点维护的是当前节点对应区间的信息,倘若每次区间都不一样,就会给处理带来一些困难。有时可以直接细分区间然后合并,此种情况线段树可以直接敲定;但有时无法通过直接划分区间来求解,如频繁询问区间第k小元素。
主席树的每个节点对应一颗线段树,此处有点抽象。在我们的印象中,每个线段树的节点维护的树左右子树下标以及当前节点对应区间的信息(信息视具体问题定)。对于一个待处理的序列a[1]、a[2]…a[n],有n个前缀。每个前缀可以看做一棵线段树,共有n课线段树;若不采用可持久化结构,带来的严重后果就是会MLE,即对内存来说很难承受。根据可持久化数据结构的定义,由于相邻线段树即前缀的公共部分很多,可以充分利用,达到优化目的,同时每棵线段树还是保留所有的叶节点只是较之前共用了很多共用节点。主席树很重要的操作就是如何寻找公用的节点信息,这些可能可能出现在根节点也可能出现在叶节点。

所谓主席树呢,就是对原来的数列[1..n]的每一个前缀[1..i](1≤i≤n)建立一棵线段树,线段树的每一个节点存某个前缀[1..i]中属于区间[L..R]的数一共有多少个(比如根节点是[1..n],一共i个数,sum[root] = i;根节点的左儿子是[1..(L+R)/2],若不大于(L+R)/2的数有x个,那么sum[root.left] = x)。若要查找[i..j]中第k大数时,设某结点x,那么x.sum[j] - x.sum[i - 1]就是[i..j]中在结点x内的数字总数。而对每一个前缀都建一棵树,会MLE,观察到每个[1..i]和[1..i-1]只有一条路是不一样的,那么其他的结点只要用回前一棵树的结点即可,时空复杂度为O(nlogn)。

摘自here

个人理解

主席树是维护一条链上的东西。

例如在序列上我们一般维护[1,i]这段序列区间,当我们需要维护[1,i+1]时,发现我们现在已经维护好了[1,i],我们现在只需要修改一条链就好了,所以每个点都会有若干根节点到它的唯一一条路径,也就是说我们新建了LogN个节点,所以理论空间复杂度是NLogN的。

经典例题区间第k大:

先考虑只有一次询问的情况:我们可以先统计出每个数出现的次数,然后二分答案。

那么多次询问呢?我们还是采用同样的思路,离散化后建立n棵权值线段树分别维护[1.i]的这个东西,在某个值的data域+1,然后对出现次数做一个前缀和,我们就可以表示[1,p]这个权值区间的答案贡献了,然后发现这个东西是可以直接相减的,用[1,y+1]减去[1,x-1]的贡献就是答案。

什么?n棵线段树?当然不需要,我们只需要对这些线段树可持久化就可以了。

主席树的第i棵树维护的是[1,i]这段区间的权值贡献,权值贡献用区间和来维护。

root[i]表示维护区间[1,i]的树的根节点是谁,当我们找到root[i]的时候,也就相当于我们找到了这颗树。

我们会发现在这里面只有叶子节点存储了信息,非叶子节点只是维护了一些东西。

主席树的标记下放,我们目的是要保留历史版本,所以不能在原来的节点上直接修改,所以我们考虑新建节点,然后建立关系.

扩展:主席树维护树上第k大:我们用类似序列的思路考虑这个问题,我们知道序列维护的是[1,i]的区间贡献,那树上呢?一个很正常的思路是维护i节点到根的区间贡献,因为这条路径是唯一的,我们在dfs的时候顺便维护它,那么显然答案就变成了ans[u]+ans[v]-ans[lca(u,v)]-ans[fa[lca(u,v)]],查找的时候还是用二分的思想找。

可持久化并查集

用可持久化线段树(or 可持久化平衡树搞)

维护当前版本下集合的关系和秩的信息.

然后启发式合并(按秩合并)

合并的时候在权值线段树的子节点加一个数,

相当于连了一条边 表示有关系存在.

显然只有在两个集合秩相同时才更新秩.

……

可持久化字典树

(待填坑)

可持久化平衡树

好像只有Treap 是可持久化的?然而我并不会orz。
(待填坑)

可持久化链表

(待填坑)

参考资料

《可持久化数据结构研究》 陈立杰

本文总阅读量