fhq-treap
对于一个集合，需要维护它，我们考虑一个包含集合中所有元素的有序序列，并使用一棵树，其中每一个子树都对应着一个子序列：
这棵树有什么性质呢？首先它是一棵二叉查找树，也就是要保持内部有序性。如何保持？它按照中序遍历是有序的。如下图，是集合 \(\{1, 4, 2, 8, 5, 7\}\) 映射到的两棵二叉查找树。
这种树上可以进行查询，例如第 \(2\) 小的数是哪个？考虑第一颗树。根的左儿子有三个节点，应该在左儿子中。递归直到确定在根上。
这样做，支持动态加入点，并且减少了遍历次数。是比较优秀的。但我们知道树的期望高度是 \(\log n\)，因此最好让树高相对“平衡”一些。
那么我们考虑给每个点赋随机权值，让每个点形成一个二元组 \((val, rand)\)。然后让这棵树对 \(rand\) 形成一个小根堆。那么这就是 treap。它是笛卡尔树的一种，当所有二元组确定下来的时候具有唯一性。
建树和一些基本的操作都可以用分裂/合并这两个 treap 上操作描述。下面介绍两种操作。
合并
考虑两棵子树，一棵上的节点都小于等于 \(k\)，另一棵上的节点都大于 \(k\)。（也就是两个互相有序的数组）需要合并为一棵树。（保证了有序能做什么？等会会说）
期望复杂度 \(O(\log n)\)。
考虑建树过程。新插入一个数 \(k\)。我们先将维护着的树分裂成 \(\le k\) 和 \(>k\) 这两棵树 \(a,b\)，且令只有单独一个节点 \(k\) 的树是 \(c\)，然后执行 \(\operatorname{merge}(\operatorname{merge}(a, c), b)\)。