fhq treap 学习笔记

今天心血来潮,来学习一下fhq treap(其实原因是本校有个OIer名叫fh,当然不是我)

简介

fhq treap 学名好像是“非旋转式treap及可持久化”。。。听上去怪怪的。其实就是可以代替LCT、BST等等码量很高的东东。

定义

操作

最基本的操作

其实都不应该叫做操作。应该类似于维护的。。。

基本操作

其实就三个啦。。。。

操作1:merge(默认x<y)

merge的操作其实就是把两棵树合并成一棵(真好!)。使用递归。按照rand出来的权值进行判断是左子树还是右子树。

操作2:split

split的操作其实就是把一棵树拆成两棵子树。当然有两种拆法,一种是按照权值,还有一种是按照节点数分。
这里的操作2是按照权值分,操作3按照节点数分。

操作3:rank

在操作2中已经说明过了,是按照节点数分(有点像其他数据结构中查找第k名的操作)

普通的操作

拿一道例题来讲吧。。。
传送门
其实操作并没有高级多少(主要是想象力。。。)

操作1:插入$x$数

这个比较好理解,我们先把树分为x,y两部分,然后把新的节点a看做是一棵树,先与x合并,合并完之后将合并的整体与y合并

操作2:删除$x$数(若有多个相同的数,因只删除一个)

首先我们把树分为x和z两部分
那么x树中的最大权值为a
再把x分为x和y两部分。
此时x中的最大权值为a-1,且权值为a的节点一定是y的根节点。
然后我们可以无视y的根节点,直接把y的左右孩子合并起来,这样就成功的删除了根节点,
最后再把x,y,z合并起来就好

操作3:查询$x$数的排名(排名定义为比当前数小的数的个数+1。若有多个相同的数,因输出最小的排名)

我们首先按照a-1的权值把树分开。
那么x树中最大的应该是a-1。
那么a的排名就是siz[x]+1

操作4:查询排名为$x$的数

//rank函数不是白吃饭的
不解释了QWQ

操作5:求$x$的前驱(前驱定义为小于$x$,且最大的数)

//rank函数真的不是白吃饭的
因为要小于a,那么我们按照a-1的权值划分,
x中最大的一定是<=a-1的,
所以我们直接输出x中最大的数就好,
(这里有一个小技巧,因为sz储存的是节点的数目,然后根据二叉查找树的性质,编号最大的就是值最大的)

操作6:求$x$的后继(后继定义为大于$x$,且最小的数)

//rank函数真的不是白吃饭的
因为要大于a,那么我们按照a的权值划分(取子树y),
y中最小的一定是>a的,
所以我们直接输出y中最小的数就好,
(像操作5一样这里有一个小技巧,因为sz储存的是节点的数目,然后根据二叉查找树的性质,编号最小的就是值最小的)

完整的代码:

写在最后

当然,fhqtreap的应用不仅限于这些,还有许多,还待我继续学习。。。 参考:zwfymqz
mocha从两位大佬的博文中窃取了许多。。。
暂无评论

发送评论


				
上一篇
下一篇