Treap

前置知识：朴素二叉搜索树

简介

Treap（树堆）是一种 弱平衡 的 二叉搜索树。它同时符合二叉搜索树和堆的性质，名字也因此为 tree（树）和 heap（堆）的组合。

其中，二叉搜索树的性质是：

• 左子节点的值（）比父节点大
• 右子节点的值（）比父节点小（当然这也是可以反过来的）

堆的性质是：

• 子节点值（）比父节点大或小（取决于是小根堆还是大根堆）

不难看出，如果用的是同一个值，那这两种数据结构的性质是矛盾的，所以我们再在搜索树的基础上，引入一个给堆的值 。对于 值，我们维护搜索树的性质，对于 值，我们维护堆的性质。其中 这个值是随机给出的。

下图就是一个 Treap 的例子（这里使用的是小根堆，即根节点的值最小）。

那我们为什么需要大费周章的去让这个数据结构符合树和堆的性质，并且随机给出堆的值呢？

要理解这个，首先需要理解朴素二叉搜索树的问题。在给朴素搜索树插入一个新节点时，我们需要从这个搜索树的根节点开始递归，如果新节点比当前节点小，那就向左递归，反之亦然。

最后当发现当前节点没有子节点时，就根据新节点的值的大小，让新节点成为当前节点的左或右子节点。

如果新插入的节点的值是随机的，那这个朴素搜索树的形状会非常的“胖”，上图的 Treap 就是一个例子。也就是说，每一层的节点比较多。

在这样的情况下，这个搜索树的层数是会比较接近 （ 为节点数）的，查询的复杂度也是 （因为只要递归这么多层就能查到）。

不过，这只是在随机情况下的复杂度，如果我们按照下面这个非常有序的顺序给一个朴素的搜索树插入节点。

1 2 3 4 5

那……

这个树就会变得非常“瘦长”（每次插入的节点都比前面的大，所以都被安排到右子节点了）：

不难看出，现在这个二叉搜索树已经退化成链了，查询的复杂度也从 变成了线性。

而 treap 要解决的正是这个问题。它通过随机化的 属性，以及维护堆性质的过程，“打乱”了节点的插入顺序。从而让二叉搜索树达到了理想的复杂度，避免了退化成链的问题。

笔者并不清楚如何去严格的证明这样随机化的过程可以让搜索树的复杂度的 期望值 保持在 ，但我们可以试着感性的去理解一下。

首先，我们需要认识到一个节点的 属性是和它所在的层数有直接关联的。再回忆堆的性质：

• 子节点值（）比父节点大或小（取决于是小根堆还是大根堆）

我们发现层数低的节点，比如整个树的根节点，它的 属性也会更小（在小根堆中）。并且，在朴素的搜索树中，先被插入的节点，也更有可能会有比较小的层数。我们可以把这个 属性和被插入的顺序关联起来理解，这样，也就理解了为什么 treap 可以把节点插入的顺序通过 打乱。

在给 treap 插入新节点时，需要同时维护树和堆的性质，为了达到这个目的，有两种方法被发明了出来，分别是旋转和分裂、合并。使用这两种方法的 treap 被分别成为有旋式 treap 和 无旋式 treap。

旋转 treap

旋转 treap 维护平衡的方式为旋转，和 AVL 树的旋转操作类似，分为 左旋 和 右旋。即在满足二叉搜索树的条件下根据堆的优先级对 treap 进行平衡操作。

旋转 treap 在做普通平衡树题的时候，是所有平衡树中常数较小的。因为普通的二叉搜索树会被递增或递减的数据卡，用 treap 对每个节点定义一个由 rand 得到的权值，从而防止特殊数据卡。同时在每次删除/插入时通过这个权值决定要不要旋转即可，其他操作与二叉搜索树类似。

大部分的树形数据结构都有指针和数组模拟两种实现方法，下面将会详细的分部分讲解指针版的代码，如果想要学习数组实现，可以拉到最下面的完整代码部分。

节点结构

旋转

旋转操作是 treap 的一个非常重要的操作，主要用来在保持 treap 树性质的同时，调整不同节点的层数，以达到维护堆性质的作用。

旋转操作的左旋和右旋可能不是特别容易区分，以下是两个较为明显的特点：

旋转操作的含义：

• 在不影响搜索树性质的前提下，把和旋转方向相反的子树变成根节点（如左旋，就是把右子树变成根节点）
• 不影响性质，并且在旋转过后，跟旋转方向相同的子节点变成了原来的根节点（如左旋，旋转完之后的左子节点是旋转前的根节点）

左旋和右旋操作是相互的，如下图。

插入

跟普通搜索树插入的过程没啥区别，但是需要在插的过程中通过旋转来维护树堆中堆的性质。

删除

主要就是分类讨论，不同的情况有不同的处理方法，删完了树的大小会有变化，要注意更新。并且如果要删的节点有左子树和右子树，就要考虑删除之后让谁来当父节点（维护 rank 小的节点在上面）。

根据值查询排名

操作含义：查询以 cur 为根节点的子树中，val 这个值的大小的排名（该子树中小于 val 的节点的个数 + 1）

根据排名查询值

要根据排名查询值，我们首先要知道如何判断要查的节点在树的哪个部分：

以下是一个判断方法的表：

注意如果在右子树，递归的时候需要对原来的 rank 进行处理。递归的时候就相当去查，在右子树中为这个排名的值，为了把排名转换成基于右子树的，需要把原来的 rank 减去左子树的大小和根节点的重复次数。

可以把所有节点想象成一个排好序的数组，或者数轴（如下），

1 -> |左子树的节点|根节点|右子树的节点| -> n
                           ^
                           要查的排名
                     ⬇转换成基于右子树的排名
1 -> |右子树的节点| -> n
       ^
       要查的排名

这里的转换方法就是直接把排名减去左子树的大小和根节点的重复数量。

查询第一个比 val 小的节点

注意这里使用了一个类中的全局变量，q_prev_tmp。

这个值是只有在 val 比当前节点值大的时候才会被更改的，所以返回这个变量就是返回 val 最后一次比当前节点的值大，之后就是更小了。

查询第一个比 val 大的节点

跟前一个很相似，只是大于小于号换了一下。

无旋 treap

无旋 treap 的操作方式使得它天生支持维护序列、可持久化等特性。

无旋 treap 又称分裂合并 treap。它仅有两种核心操作，即为 分裂 与 合并。通过这两种操作，在很多情况下可以比旋转 treap 更方便的实现别的操作。下面逐一介绍这两种操作。

分裂（split）

按值分裂

分裂过程接受两个参数：根指针 、关键值 。结果为将根指针指向的 treap 分裂为两个 treap，第一个 treap 所有结点的值（）小于等于 ，第二个 treap 所有结点的值大于 。

该过程首先判断 是否小于 的值，若小于，则说明 及其右子树全部小于 （ 可能等于 ），属于第二个 treap。当然，也可能有一部分的左子树的值大于 ，所以还需要继续向左子树递归地分裂。对于大于 的那部分左子树，我们把它作为 的左子树，这样，整个 上的节点都是大于 的。

相应的，如果 大于等于 的值，说明 的整个左子树以及其自身都小于 ，属于分裂后的第一个 treap。并且， 的部分右子树也可能有部分小于 ，因此我们需要继续递归地分裂右子树。把小于 的那部分作为 的右子树，这样，整个 上的节点都小于 。

下图展示了 的值小于等于 时按值分裂的情况。²

按排名分裂

比起按值分裂，这个操作更像是旋转 treap 中的根据排名（某个节点的排名是树中所有小于此节点值的节点的数量 ）查询值：

此函数接受两个参数，节点指针 和排名 ，返回分裂后的三个 treap。

其中，第一个 treap 中每个节点的排名都小于 ，第二个的排名等于 ，并且第二个 treap 只有一个节点（不可能有多个等于的，如果有的话会增加 Node 结构体中的 cnt），第三个则是大于。

此操作的重点在于判断排名和 相等的节点在树的哪个部分，这也是旋转 treap 根据排名查询值操作时的重要部分，在前文有非常详细的解释，这里不过多讲解。

并且，此操作的递归部分和按值分裂也非常相似，这里不赘述。

合并（merge）

合并过程接受两个参数：左 treap 的根指针 、右 treap 的根指针 。必须满足 中所有结点的值小于等于 中所有结点的值。一般来说，我们合并的两个 treap 都是原来从一个 treap 中分裂出去的，所以不难满足 中所有节点的值都小于

在旋转 treap 中，我们借助旋转操作来维护 符合堆的性质，同时旋转时还不能改变树的性质。在无旋 treap 中，我们用合并达到相同的效果。

因为两个 treap 已经有序，所以我们在合并的时候只需要考虑把哪个树“放在上面”，把哪个“放在下面”，也就是是需要判断将哪个一个树作为子树。显然，根据堆的性质，我们需要把 小的放在上面（这里采用小根堆）。

同时，我们还需要满足搜索树的性质，所以若 的根结点的 小于 的，那么 即为新根结点，并且 因为值比 更大，应与 的右子树合并；反之，则 作为新根结点，然后因为 的值比 小，与 的左子树合并。

插入

在无旋 treap 中，插入，删除，根据值查询排名等基础操作既可以用普通二叉查找树的方法实现，也可以用分裂和合并来实现。通常来说，使用分裂和合并来实现更加简洁，但是速度会慢一点³。为了帮助更好的理解无旋 treap，下面的操作全部使用分裂和合并实现。

在实现插入操作时，我们利用了分裂操作的一些性质。也就是值小于等于 的节点会被分到第一个 treap。

所以，假设我们根据 分裂当前这个 treap。会有下面两棵树，并符合以下条件：

其中 表示分裂后所有被分到第一个 treap 的节点的集合， 则是第二个。

如果我们再按照 继续分裂 ，那么会产生下面两棵树，并符合以下条件：

其中 表示 分裂后所有被分到第一个 treap 的节点的集合， 则是第二个。并且上面的式子中，后半部分的 来自于 所符合的条件 。

不难发现，只要 和节点的值是一个整数（大多数使用场景下会使用整数）那么符合 条件的节点只有一个，也就是值等于 的节点。

在插入时，如果我们发现符合 的节点存在，那就可以直接增加重复次数，否则，就新开一个节点。

注意把树分裂好了还需要用合并操作把它“粘”回去，这样下次还能继续使用。并且，还需要注意合并操作的参数顺序是有要求的，第一个树的所有节点的值都需要小于第二个。

删除

删除操作也使用和插入操作相似的方法，找到值和 相等的节点，并且删除它。

根据值查询排名

排名是比这个值小的节点的数量 ，所以我们根据 分裂当前树，那么分裂后的第一个树就符合：

如果树的值和 为整数，那么 就包含了所有值小于 的节点。

根据排名查询值

调用 split_by_rk() 函数后，会返回分裂好的三个 treap，其中第二个只包含一个节点，它的排名等于 ，所以我们直接返回这个节点的 。

查询第一个比 val 小的节点

可以把这个问题转化为，在比 小的所有节点中，找出排名最大的。我们根据 来分裂这个 treap，返回的第一个 treap 中的节点的值就全部小于 ，然后我们调用 qval_by_rank() 找出这个树中值最大的节点。

查询第一个比 val 大的节点

和上个操作类似，可以把这个问题转化为，在比 大的所有节点中，找出排名最大的。那么根据 分裂后，返回的第二个 treap 中的所有节点的值就大于 。

然后我们去查询这个树中排名为 的节点（也就是值最小的节点）的值，就可以成功查到第一个比 大的节点。

建树（build）

将一个有 个节点的序列 转化为一棵 treap。

可以依次暴力插入这 个节点，每次插入一个权值为 的节点时，将整棵 treap 按照权值分裂成权值小于等于 的和权值大于 的两部分，然后新建一个权值为 的节点，将两部分和新节点按从小到大的顺序依次合并，单次插入时间复杂度 ，总时间复杂度 。

在某些题目内，可能会有多次插入一段有序序列的操作，这是就需要在 的时间复杂度内完成建树操作。

方法一：在递归建树的过程中，每次选取当前区间的中点作为该区间的树根，并对每个节点钦定合适的优先值，使得新树满足堆的性质。这样能保证树高为 。

方法二：在递归建树的过程中，每次选取当前区间的中点作为该区间的树根，然后给每个节点一个随机优先级。这样能保证树高为 ，但不保证其满足堆的性质。这样也是正确的，因为无旋式 treap 的优先级是用来使 merge 操作更加随机一点，而不是用来保证树高的。

方法三：观察到 treap 是笛卡尔树，利用笛卡尔树的 建树方法即可，用单调栈维护右链即可。

无旋 treap 的区间操作

建树

无旋 treap 相比旋转 treap 的一大好处就是可以实现各种区间操作，下面我们以文艺平衡树的 模板题 为例，介绍 treap 的区间操作。

您需要写一种数据结构（可参考题目标题），来维护一个有序数列。

其中需要提供以下操作：翻转一个区间，例如原有序序列是 ，翻转区间是 的话，结果是 。 对于 的数据，（初始区间长度）（翻转次数）

在这道题目中，我们需要实现的是区间翻转，那么我们首先需要考虑如何建树，建出来的树需要是初始的区间。

我们只需要把区间的下标依次插入 treap 中，这样在中序遍历（先遍历左子树，然后当前节点，最后右子树）时，就可以得到这个区间⁴。

我们知道在朴素的二叉查找树中按照递增的顺序插入节点，建出来的树是一个长链，按照中序遍历，自然可以得到这个区间。

如上图，按照 的顺序给朴素搜索树插入节点，中序遍历时，得到的也是 。

但是在 treap 中，按增序插入节点后，在合并操作时还会根据 调整树的结构，在这样的情况下，如何确保中序遍历一定能正确的输出呢？

可以参考 笛卡尔树的单调栈建树方法 来理解这个问题。

设新插入的节点为 。

首先，因为时递增的插入节点，每一个新插入的节点肯定会被连接到 treap 的右链（即从根结点一直往右子树走，经过的结点形成的链）上。

从根节点开始，右链上的节点的 是递增的（小根堆）。那我们可以找到右链上第一个 大于 的节点，我们叫这个节点 ，并把这个节点换成 。

因为 一定大于这个树上其他的全部节点，我们需要把 以及它的子树作为 的左子树。并且此时 没有右子树。

可以发现，中序遍历时 一定是最后一个被遍历到的（因为 是右链中的最后一个，而中序遍历中，右子树是最后被遍历到的）。

下图是一个 treap 根据递增顺序插入 号节点时，插入 号节点时的变化，可以用这张图更好的理解按照增序插入的过程。

区间翻转

翻转 这个区间时，基本思路是将树分裂成 三个区间，再对中间的 进行翻转⁴。

翻转的具体操作是把区间内的子树的每一个左，右子节点交换位置。如下图就展示了翻转上图中 treap 的 和 区间后的 treap。

注意如果按照这个方法翻转，那么每次翻转 区间时，就会有 个节点会被交换位置，这样频繁的操作显然不能满足 的数据范围，其 的单次翻转复杂度甚至不如暴力（因为我们除了需要花线性时间交换节点外，还需要在树中花费 的时间找到需要交换的节点。

再观察题目要求，可以发现因为只需要最后输出操作完的区间，所以并不需要每次都真的去交换。如此一来，便可以使用线段树中常用的懒标记（lazy tag）来优化复杂度。交换时，只需要在父节点打上标记，代表这个子树下的每个左右子节点都需要交换就行了。

在线段树中，我们一般在更新和查询时下传懒标记。这是因为，在更新和查询时，我们想要更新/查询的范围不一定和懒标记代表的范围重合，所以要先下传标记，确保查到和更新后的值是正确的。

在无旋 treap 中也是一样。具体操作时我们会把 treap 分裂成前文讲到的三个树，然后给中间的树打上懒标记后合并这三棵树。因为我们想要翻转的区间和懒标记代表的区间不一定重合，所以要在分裂时下传标记。并且，分裂和合并操作会造成每个节点及其懒标记所代表的节点发生变动，所以也需要在合并前下传懒标记。

换句话说，是当树的结构发生改变的时候，当我们进行分裂或合并操作时需要改变某一个点的左右儿子信息时之前，应该下放标记，而非之后，因为懒标记是需要下传给儿子节点的，但更改左右儿子信息之后若懒标记还未下放，则懒标记就丢失了下放的对象。⁵

以下为代码讲解，代码参考了⁴。

因为区间操作中大部分操作都和普通的无旋 treap 相同，所以这里只讲解和普通无旋 treap 不同的地方。

下传标记

需要注意这里的懒标记代表需要把这个树中的每一个子节点交换位置。所以如果当前节点的子节点也有懒标记，那两次翻转就抵消了。如果子节点不需要翻转，那么这个懒标记就需要继续被下传到子节点上。

分裂

注意在这个题目中，因为翻转操作，treap 中的 会不符合二叉搜索树的性质（见区间翻转部分的图），所以我们不能根据 来判断应该往左子树还是右子树递归。

所以这里的分裂跟普通无旋 treap 中的按排名分裂更相似，是根据当前树的大小判断往左还是右子树递归的，换言之，我们是按照开始时这个节点在树中的位置来判断的。

返回的第一个 treap 中节点的排名全部小于等于 ，而第二个 treap 中节点的排名则全部大于 。

合并

唯一需要注意的是在合并前下传懒标记

区间翻转

和前面介绍的一样，分裂出 三个区间，然后对中间的区间打上标记后再合并。

中序遍历打印

要注意在打印时要下传标记。

完整代码

旋转 treap

指针实现

数组实现

以下是 bzoj 普通平衡树模板代码，使用数组实现。

无旋 treap

指针实现

无旋 treap 的区间操作

指针实现

例题

普通平衡树

文艺平衡树（Splay）

「ZJOI2006」书架

「NOI2005」维护数列

CF 702F T-Shirts

参考资料与注释