本文章同步发布至 浅谈 fhq-treap —— 或是 Splay 的不二选择？
一、从 BST 谈起
BST 的意思是二叉搜索树，它满足对于所有子树的根节点 \(x\)，满足 \(v_{rson} > v_x > v_{lson}\)，也就是说，它的中序遍历为一个有序的序列。
这就是一个 BST，其的中序遍历为 1 3 4 5 6 7 8。
BST 的实现很简单，但由于它的结构不稳定，如上面两张图都是同一个中序遍历，所以会被构造数据卡到 \(O(n)\)，但随机数据下仍然为 \(O(\log_2n)\)。
二、关于 treap
treap 上的每一个点有两个值：权值和键值。
- 权值：我们采用 BST 进行维护，使得 \(v_{rson} > v_x > v_{lson}\)。
- 键值：我们随机化键值，然后采用小根堆维护键值，使得 \(g_x < g_{lson},g_{rson}\)。
为什么这棵树的结构是一定的？我们发现 treap 的根节点的键值一定最小，也就是我们的根节点确定了。
此时我们左右两棵子树的权值范围确定了，再根据键值的限制，左右儿子也会确定下来，同理，这颗树也会确定下来。
确定好结构后，我们的 treap 就很好实现了，treap 分为有旋和无旋两种，有旋就是 Splay 等，这里我们将以 fhq-treap 代表的无旋树。
二-ex、关于复杂度
对于权值我们是无法控制的，但对于键值，根据随机化我们的 Heap 高度是 \(\log_2n\)，也就是这颗树的高度被 Heap 所限，为 \(\log_2n\)，此时的操作复杂度就为 \(O(\log_2n)\)。
三、分裂与合并
fhq-treap 的优点是编写简单，可以实现很多操作，但缺点是需要利用多次分裂与合并操作来进行维护，常数大。
1.分裂
我们的分裂操作是将权值小于等于 \(x\) 的树从原树上分裂下来，将一颗 \([l,r]\) 范围内的树变为 \([l,x]\) 与 \([x+1,r]\)，将一颗 treap 分裂为两颗 treap。
由于 treap 的性质，我们发现分裂后的两颗 treap 的结构也是一定的！
我们来思考如何分裂：
-
对于一棵以 \(u\) 为根的子树，根据 BST 的特点，我们发现若 \(u\) 的左儿子 \(u_{lson}\) 权值 \(val \le x\)，那么它的左子树一定也小于 x，此时我们可以把这颗树先分离出来（以 \(x \le 5\) 为例）：
-
对于右子树的操作和左子树一样，但是对于右儿子的权值 \(\le x\)，我们只将右儿子与其的左子树加入新树，而右儿子的右子树需要再次递归判断。
-
对于左儿子的权值 \(\ge x\)，我们需要递归它左儿子的左子树，对于右儿子也一样。
