【转载】史上最简单的平衡树——无旋Treap

崔晓明发布于2019-07-01 14:08 / 733人阅读

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

【转载】史上最简单的平衡树——无旋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

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

GPU云服务器云服务器史上最史上最详细跨境电商erp 平衡树 python 平衡树

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/31839.html

LuxTdmZtIC

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

CoffeX 2019-08-02 15:24 评论0 收藏0
LuxTdmZtIC

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

tuantuan 2019-08-23 18:22 评论0 收藏0
LuxTdmZtIC

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

roundstones 2019-08-30 11:17 评论0 收藏0
架构～微服务 - 收藏集 - 掘金

摘要：它就是史上最简单的教程第三篇服务消费者后端掘金上一篇文章，讲述了通过去消费服务，这篇文章主要讲述通过去消费服务。概览和架构设计掘金技术征文后端掘金是基于的一整套实现微服务的框架。 Spring Boot 配置文件 – 在坑中实践 - 后端 - 掘金作者：泥瓦匠链接：Spring Boot 配置文件 – 在坑中实践版权归作者所有，转载请注明出处本文提纲一、自动配置二、自定义属性三、ran...

church 2019-06-24 17:54 评论0 收藏0
史上最简单的SpringCloud教程 | 第三篇: 服务消费者（Feign）

摘要：一简介是一个声明式的服务客户端，它使得写服务变得更简单。同时支持可插拔的编码器和解码器。对添加了支持，同时在中次用相同的。转载请标明出处： http://blog.csdn.net/forezp/a...本文出自方志朋的博客上一篇文章，讲述了通过restTemplate+ribbon去消费服务，这篇文章主要讲述通过feign去消费服务。一、Feign简介 Feign是一个声明式的...

0x584a 2019-08-16 10:31 评论0 收藏0