LuxTdmZtIC

摘要：转载史上最简单的平衡树无旋作者博客地址使用此文件时请保留上述信息谢谢合作觉得文章不错请点击链接为博客点赞高能预警所有示例代码都是数组版的欢迎前置知识线段树请确保你完全理解最基础的线段树和区间加法和区间求和一简介无旋又称是范浩强大佬发明的一种

前置知识:线段树!请确保你完全理解最基础的线段树和LazyTag(区间加法和区间求和).

无旋Treap,又称fhq_treap,是范浩强大佬发明的一种强力数据结构.

总的来说,它可以支持一切Treap和Splay等平衡树的操作,支持可持久化(但是这篇博客不会讲),常数远小于Splay,但是处理LCT问题略比Splay逊色,以至于我到现在还不会.

对于初学者来说,它比Splay好学,比Treap好用,实在不失为一个性价比极高的数据结构.

首先让我们来复习一下平衡树们的祖宗——二叉搜索树的性质:

递归定义,空树是一棵二叉搜索树,二叉搜索树的左子树的最大点权小等于根的点权小等于右子树的最小点权,二叉搜索树的左右子树也是二叉搜索树.

二叉搜索树的插入,删除,搜索等操作都容易被极端数据卡满复杂度,这时我们就需要各种神奇操作来确保它的树高期望大小为log级别.我们直接看无旋Treap是如何操作的(因为其他几种我不大会):

无旋Treap有两种基本操作:

将树分为两棵树,其中树A的最大点权小等于树B的最小点权.因为树高期望为log,所以单次操作的复杂度期望为log.

将两棵树合为一棵树,其中树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剖出你需要操作的区间代表的子树,然后在根节点打标记,然后合并即可.

需要支持插入,删除,查元素排名和排名元素,查前驱后继.

模板题,把上面除了区间操作以外的东西实现好即可.

AC代码:https://www.luogu.org/recordn...
开启O2优化,洛谷更新数据后262ms

一个1到N的排列,M次操作,每次翻转一个区间,求最后的排列.

只用实现区间操作即可,具体如何打标记,下传标记请看代码.

AC代码:https://www.luogu.org/recordn...
开启O2优化,洛谷更新数据后488ms

区间加,区间求和.

这个例子是为了方便大家理解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

仅供学习交流使用!!!谢谢配合!!!