讲完了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); } }