史上最简单的平衡树：无旋Treap

与下文无关的补充说明：

本文最早发布在牛客发帖区，链接https://ac.nowcoder.com/discuss/177864 ；最近因为牛客加入了博客功能就搬迁到了我自己的博客，pdf文件中未作修改。还有就是，撰写本文时迷恋英文符号……对于您阅读时产生的恶心在下深感抱歉233

作者:fzszkl

博客地址:https://blog.nowcoder.net/fzszkl

使用此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}$ 乘一个组合数什么的).