0.引言
要懂得 FHQ-Treap（无旋 Treap），我们必须先懂（有旋）Treap。
要懂得 Treap，我们必须先懂平衡树。
要懂得平衡树，我们必须先懂 BST（二叉搜索树）。
1.BST
BST，二叉搜索树，首先得是一颗二叉树。\O/\O/\O/\O/\O/\O/
其次，这颗树还得满足一个节点比它的左儿子大，比右儿子小。
那么维护这棵树就很简单了，只需要递归模拟即可。
一颗示例 BST，其中插入顺序为 [114,5,514,1,500,501,7][114,5,514,1,500,501,7][114,5,514,1,500,501,7]（可能的一种）：
BST模板（洛谷P5076）
2.平衡树
但是，我们注意到如果顺序趋近于单调递增/递减，那么它的复杂度就会趋近于单次 O(n)O(n)O(n)。
一颗示例 O(n)O(n)O(n) 的 BST，其中插入顺序为 [1,2,3,4,5][1,2,3,4,5][1,2,3,4,5]：
明显的，这颗树最优高度是 logn\log{n}logn 的，而平衡树就是维护高度为 O(logn)O(\log{n})O(logn)（注意，常数可能大于 111，所以是带 O 的），从而使得每个操作都为 O(logn)O(\log{n})O(logn) 的复杂度（因为 BST 操作最多会遍历树高度）。
常见的平衡树有：Splay、（有旋）Treap、FHQ-Treap、红黑树（set 和 map 内部使用的平衡树）、SBT（Size Balanced Tree，好像是理论上最快的平衡树实际被红黑树暴打）、AVL 树、替罪羊树（需要特定的不平衡率保持常数，是弱平衡的，但是有时候其它平衡树不好保持平衡，而替罪羊树比较方便）、WBLT（据说好像有的能被卡到 O(n)O(n)O(n) 单次）、B 树（看算导知道的，主要用于硬盘）。
3.替罪羊树
既然说到了平衡树，这里先引入一个比较简单的平衡树——替罪羊树。
先分析一下为什么普通 BST 能被卡：一颗子树比另外一颗大太多，顺序趋近于单调递增/递减就会让一颗子树几乎是空的而另一颗几乎包括所有节点。于是乎我们可以当一颗子树占它和它兄弟树大小之和的 α\alphaα（不平衡率，常数）时，就视为这棵树已经不平衡了（比它的兄弟大太多），重建它。
重建方法：先中序遍历这整颗树，得到原数组，再递归，选取中间节点为父亲，左右两部分为子树继续递归。可以证明这样构建树是完全平衡的，是 logn\log{n}logn 高度的。
然后对于其它操作与普通 BST 一样，只要在插入时看不平衡率有没有达到 α\alphaα 就行。
但是 α\alphaα 对复杂度至关重要，经测验一般设置为 0.70.70.7 或 0.750.750.75。
替罪羊树虽简单，但复杂度差点，而且一般难以拓展，请读者自行使用替罪羊树写出模板题，也可以自行了解替罪羊树的应用。
4.TREAP
既然在趋近有序时时间复杂度差，那么我们就反其道而行之，尽可能让它无序。
可以想到随机打乱，这样就可以无序了，可以证明这样构建 BST 高度是期望 O(logn)O(\log{n})O(logn) 的（虽然是期望，但实际也很快）。
但是随机打乱需要在知道所有的情况下，如何动态解决？就是 Treap 的思路。
我们使用开始的例子，在节点旁标注其插入顺序中的位置：
（标注错误，777 旁应为 777）
惊人的发现，父节点的插入顺序比儿子（可以扩大到所有子孙节点）先（也可以通过 BST 的模拟方式证明）！也就是说 BST 在插入顺序上是一个（小根）堆！
这也是 Treap 名字的由来，Treap=Tree+Heap。
那么我们就可以在插入时随机一个顺序（变量维护，下文中将顺序称为优先级），然后同时使用 BST 的模拟和堆的维护来维护 Treap。
5.FHQ-TREAP
先膜拜 FHQ-Treap 的发明人 FHQ（范浩强）。
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
FHQ-Treap 并不需要晦涩难懂的旋转操作（而且天生适合序列操作），因为 Treap 是通过随机的性质本身来保持平衡的，和维护（注意，不是保持）平衡的操作无关。
FHQ-Treap 的基本操作只有两个，是分裂与分化合并。
分裂并不涉及优先级，仅仅是将一颗 Treap 分成 ≤x\le x≤x 和 >x>x>x 的两部分，因为 BST 和堆的结构都是递归的，所以 Treap 的结构也是递归的，故分裂操作并不会影响平衡性。实现见下文，递归即可。
合并是分裂的逆操作，可以将两颗 Treap 合并成一颗 Treap，约定合并左树的根值小于右树，那么如果左数优先级大于右树，根据 Treap 性质，递归合并左树右儿子和右树，反之递归合并右树左儿子和左树。实现见下文。
其它操作：插入 xxx，分裂出 ≤x\le x≤x 和 >x>x>x，新建值为 xxx 的节点（节点一定是 Treap），合并到左树中，再将左树与右树合并；删除 xxx，分裂出 ≤x\le x≤x 和 >x>x>x，再从左树分裂出 ≤x−1(<x)\le x-1(<x)≤x−1(<x) 和 >x−1(>x)≤x+1>x-1(>x)\le x+1>x−1(>x)≤x+1（即 =x=x=x）的，合并 <x<x<x 和 >x>x>x 的，把 =x=x=x 弃之不理即可；xxx 排名，分裂出 ≤x−1(<x)\le x-1(<x)≤x−1(<x) 和 >x−1(≥x)>x-1(\ge
x)>x−1(≥x) 的，左树大小加一即为排名；第 kkk 小，不用分裂或合并，和 BST 一样就行；前驱，分裂出 ≤x−1(<x)\le x-1(<x)≤x−1(<x) 和 >x−1(≥x)>x-1(\ge x)>x−1(≥x) 的，左树使用第 kkk 小求出最大的即可；后继，分裂出 ≤x\le x≤x 和 >x>x>x 的，右树使用第 kkk 小求出最小的即可。
6.应用
简单运用
洛谷P3369&P6136
思路
平衡树板子，上文已阐述。
加强版与普通版并无差别，只需加个异或。
代码
这里为 FHQ-Treap 在普通版的代码
洛谷P1908
思路
考虑每个值 xxx，答案即为 xxx 前面的数 >x>x>x 的数的数量。灵活运用无旋 Treap 的分裂，将树分为 ≤x\le x≤x 和 >x>x>x 的两棵树，答案即为右树大小之和。
代码
洛谷P3871
思路
操作一就在平衡树中加入 aaa，操作二求第 ⌈n2⌉\lceil\frac{n}{2}\rceil⌈2n ⌉ 大即可。
代码
序列处理
知识：排名分裂
排名分裂比起普通分裂，不一样的就是，它分裂出的是前 xxx 个数所形成的 Treap 以及后面所形成的 Treap。方法大同小异
合并直接和平时一样。
洛谷P3391
思路
使用排名分裂裂出前 rrr 树和剩下的，再在左树中分裂出前 l−1l-1l−1 个，剩下的就是 [l,r][l,r][l,r]。
然后借鉴线段树，增加懒标记，这样就能从 O(n)O(n)O(n) 变成 O(logn)O(\log{n})O(logn)。
（翻转）其法：在序列中随便选择一个数，再将左右旁两个区间递归进行这个操作（可以证明）。这样就可以使用懒标记来加速了。
代码
洛谷P4008
思路
用变量维护光标。
插入操作就合并出整个字符串的 Treap，再分裂出前光标 −1-1−1 和剩下的，合并前光标 −1-1−1 和这个 Treap，再合并到剩下的里面。
删除操作，分裂出前光标 −1-1−1 和剩下的，在右树种分裂出前 nnn 个，把开始的左树和这里剩下的合并就行，中间的弃之不理就可以。
输出就分裂出前光标 −1-1−1 和剩下的，在右树中分裂出前 nnn 个和剩下的，在右树分裂出的左树中中序遍历输出，最后按顺序合并即可。
代码
某OJ第二难比赛的T6
题意
nnn 长的字符串 sss，qqq 次操作：操作一，将区间 [l,r][l,r][l,r] 内的字符循环右移 xxx 位；操作二，整个字符串循环右移 xxx 位。
思路
操作 222 只要把前 n−xn-xn−x 个裂成 LLL，剩下后 xxx 就是 RRR，合并 RRR 和 LLL 就行。
操作 111 给每个节点加个懒标记（偏移），分裂合并的时候 pushdown（下发） 和 pushup（更新大小） 就行。
代码
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
洛谷版传送门
