共计 2552 个字符，预计需要花费 7 分钟才能阅读完成。
【转载】史上最简单的平衡树——无旋 Treap
作者:fzszkl
博客地址:https://ac.nowcoder.com/discu…
使用此 PDF 文件时请保留上述信息! 谢谢合作! 觉得文章不错请点击链接为博客点赞!
高能预警: 所有示例代码都是数组版的, 欢迎 copy!
前置知识: 线段树! 请确保你完全理解最基础的线段树和 LazyTag(区间加法和区间求和).
一、简介
无旋 Treap, 又称 fhq_treap, 是范浩强大佬发明的一种强力数据结构.
总的来说, 它可以支持一切 Treap 和 Splay 等平衡树的操作, 支持可持久化 (但是这篇博客不会讲), 常数远小于 Splay, 但是处理 LCT 问题略比 Splay 逊色, 以至于我到现在还不会.
对于初学者来说, 它比 Splay 好学, 比 Treap 好用, 实在不失为一个性价比极高的数据结构.
二、详解
首先让我们来复习一下平衡树们的祖宗——二叉搜索树的性质:
递归定义, 空树是一棵二叉搜索树, 二叉搜索树的左子树的最大点权小等于根的点权小等于右子树的最小点权, 二叉搜索树的左右子树也是二叉搜索树.
二叉搜索树的插入, 删除, 搜索等操作都容易被极端数据卡满复杂度, 这时我们就需要各种神奇操作来确保它的树高期望大小为 log 级别. 我们直接看无旋 Treap 是如何操作的 (因为其他几种我不大会):
无旋 Treap 有两种基本操作:
(1) 分裂 Split
将树分为两棵树, 其中树 A 的最大点权小等于树 B 的最小点权. 因为树高期望为 log, 所以单次操作的复杂度期望为 log.
(2) 合并 Merge
将两棵树合为一棵树, 其中树 A 的最大点权小等于树 B 的最小点权. 为了保证树高期望为 log, 我们要想办法随机合并.
没了 (卧槽你啥都没说啊).
好吧, 为了博客过审, 还是再来仔细讲一下.
以下实例代码中,0 代表空节点,Pushdown 代表下传标记,Pushup 代表向上更新.
先来看一眼 Split:
void Split(int Nod , int Siz , int &A , int &B) {if( Nod == 0) return (void)(A = B = 0) ;
Pushdown(Nod) ;
if(Siz <= Size[Ls[Nod]] ) B = Nod , Split(Ls[Nod] , Siz , A , Ls[Nod] ) ;
else A = Nod , Split(Rs[Nod] , Siz - Size[Ls[Nod]] - 1 , Rs[Nod] , B ) ;
Pushup(Nod) ;
}Nod 为当前准备拆开的节点,A 和 B 为左右子树根节点的指针,Siz 为拆分出的左子树的大小.
翻译成人话: 当拆分的大小不超过左子树大小时, 当前节点会被分配到右子树 (B=Nod), 然后进入左子树进行拆分, 拆分下来的左子树仍旧传到 A, 拆下来的右子树则作为当前节点的左子树, 否则同理.
首先确保你对指针有初步的认识 (因为我也只有初步的认识), 然后确保你牢记了二叉搜索树的性质 (这样你才能理解为什么要这样拆分, 不论如何拆分都不能改变节点从小到大中序排序的定律).
如果是按照权值拆分 Split, 稍微改一下就好了.
然后看一眼 Merge:
int Merge(int A , int B) {if( A == 0 or B == 0) return A | B ;
register int Ans ;
Pushdown(A) ;
Pushdown(B) ;
if(Pos[A] > Pos[B] ) Rs[A] = Merge(Rs[A] , B ) , Ans = A ;
else Ls[B] = Merge(A , Ls[B] ) , Ans = B ;
Pushup(Ans) ;
return Ans ;
}Pos 是随机权值, 这样我们就可以保证树高的期望为 log(蒟蒻口胡: 因为形成长度为 n 的链的概率大概为 $\frac{1}{2^n}$ 乘一个组合数什么的 ).
两种合并方法是等价的. 都是把其中一个节点当作这一步的根节点, 另一个节点和根节点的子树递归合并. 请再次回忆二叉搜索树的性质, 所以我们一定要保证 A 在 B 的 ” 左边 ”.
一定要注意啊,Merge(A,B) 和 Merge(B,A) 天差地别啊!
有了这两种看上去就特别 nb 的操作, 我们组合一下, 就可以完成很多 nb 的事情啦~
常规操作
查排名, 查前驱后继等操作同普通平衡树, 在树上 dfs 即可. 不过为了体现无旋 Treap 的优越, 下方给出的实例代码是利用两种基本操作实现的, 优点在于直观, 好写, 缺点在于比起直接 dfs 的话常数略大.
插入节点
新建一个节点, 然后根据权值拆成左右子树, 然后 Merge(Merge( 左, 新节点), 右 ) 即可.
删除节点
根据权值拆成左右子树和要拆除的节点, 然后直接 Merge(左, 右) 即可.
区间操作
一般来讲是通过 Split 剖出你需要操作的区间代表的子树, 然后在根节点打标记, 然后合并即可.
三、喜闻乐见小例题
(1) 洛谷 3369 普通平衡树:https://www.luogu.org/problem…
需要支持插入, 删除, 查元素排名和排名元素, 查前驱后继.
模板题, 把上面除了区间操作以外的东西实现好即可.
AC 代码:https://www.luogu.org/recordn…
开启 O2 优化, 洛谷更新数据后 262ms
(2) 洛谷 3391 文艺平衡树:https://www.luogu.org/problem…
一个 1 到 N 的排列,M 次操作, 每次翻转一个区间, 求最后的排列.
只用实现区间操作即可, 具体如何打标记, 下传标记请看代码.
AC 代码:https://www.luogu.org/recordn…
开启 O2 优化, 洛谷更新数据后 488ms
(3) 洛谷 3372 线段树:https://www.luogu.org/problem…
区间加, 区间求和.
这个例子是为了方便大家理解 LazyTag, 做好线段树到平衡树, 或者普通平衡树到区间平衡树的衔接, 特意忍辱负重写了这篇代码. 是不是超级良心~
AC 代码:https://www.luogu.org/recordn…
开启 O2 优化, 洛谷更新数据后 642ms
为什么最水的一题代码反而最慢啊, 新数据也太强了吧.
四、售后保障
什么? 博客太烂了看不懂?
推荐阅读:http://iwo.im/?q=%E6%97%A0%E6…
(↑↑↑看完你会回来点赞的.)
本文 PDF 文件:
链接：https://pan.baidu.com/s/1vR9d…
提取码：mnc4
仅供学习交流使用!!! 谢谢配合!!!
