Treap

讲完了treap和splaytree，接下来讲把这两的思想混合在一起的 FHQ Treap，据说作者是范浩强。 splay其实还有两个操作split和merge没有介绍，我打算把这两放在这里一并介绍 Split和Merge Split就是把树按某个条件划分成两棵子树，如果是查找树，就按某个值划分为小于它的以及大于等于它的（等于号取哪边怎么好写怎么来就是），如果是序列维护，那就按照rank来划分。而merge操作则正好相反，把两棵子树合并成为一棵。所以，如果我们需要对某个区间做操作，那么我们就把那个区间Split出来，操作好了后（打懒惰标记，或取出结果）再Merge回去就行了，与splay操作的思路是差不多的。不过为了在split再merge后能间接对树的平衡性优化，我们不能简单地merge，要套用Treap的随机数法，我们先来看怎么split。 先定义好接口void split(int tp, int k, int &x, int &y)，x是返回的左子树，y是返回的右子树，接着我们需要递归split，如果划分点在左子树，那么y一定是根，反之划分点在右子树，那么x一定是根。确定了其中一个，在递归调用的时候，假如y确定了，于是还没确定的，就是x以及根节点的左子树的指向，所以把这两传参就行了，时间复杂度 $O(logn)$ ，具体代码如下： // 维护序列的实现 void split(int tp, int k, int &x, int &y) { if (!tp) { x = y = 0; return; } pushdown(tp); if (k <= nodes[ch(tp, 0)].sz) { y = tp; split(ch(tp, 0), k, x, ch(tp, 0)); update(y); } else { x = tp; split(ch(tp, 1), k - nodes[ch(tp, 0)].sz - 1, ch(tp, 1), y); update(x); } }

平衡树除了用来对存在偏序关系的数据进行维护，还能用于对序列维护，相当于一个数组。阅读本文你需要先看完上一篇关于treap的文章。 序列维护 在之前的文章，我们介绍过使用树状数组，以及线段树来维护一个序列，可以做区间操作及区间求和，但它们都存在一个缺点，不能动态插入数据。那我们怎么样才能通过平衡树来维护序列呢，之前我们有一个size字段能快速找第k大（或树的中序遍历第k个元素），而旋转操作并不会改变元素之间的相对顺序，那么我们就通过它直接插入到第k个元素的前面，这样我们插入的时候就不再通过要插入的值本身的大小关系，而需要多加一个参数k决定插入的位置。当平衡树用于维护序列的时候，就不用考虑元素相等的问题了。这样我们把元素相等处理的代码删除并修改基本操作的代码就能得到第一个能维护序列的基本模板，以下模板使用Treap修改得来。

这里之所以把这两个放在一起讲，是因为它们实在是相似度很高（至少在竞赛领域），都需要求kth和指定元素的rank（Treap的话可有可无，但通常会需要）。不过如果你没有写过树，强烈建议你自己通过理解来写一遍。 BST 首先，Treap和SBT都属于BST的一种，BST就是二叉搜索树，它满足的特点是： 二叉树 没有两个节点的值相等 任意子树的根节点的值都比左子树所有节点的值要大 任意子树的根节点的值都比右子树所有节点的值要小 任意子树均为二叉搜索树 如果我们实在需要支持多个相同值放在树里面，那么有两种情况，如果那些相同值是确实完全没有区别（例如int），那么只需要在每个节点多加一个字段记录这个值出现的次数就可以了，但如果这些值只有偏序关系，可能不是严格相等，存在其它非比较字段，那么我们就再在每个节点增加一个next域做成一个链表即可。