标题是吸引你点进来的
Case 1
LCT 的 access 操作应该可以实现某种区间覆盖的操作（听同学讲的，具体的还待讨论）
Case 2
众所周知，可并堆中左偏树合并是这样写的（记 \(dist\) 为 \(rd\)）：
merge(A, B)
if !A: return B
if !B: return A
if B.val > A.val
swap(A, B)
A.rs <- merge(A.rs, B)
if (A.rs.rd > A.ls.rd)
swap(A.ls, A.rs)
A.rd = A.rs.rd + 1
return A
你将其与斜堆合并代码 diff 一下就会发现，斜堆就是左偏树删去 if (A.rs.rd > A.ls.rd)、A.rd = A.rs.rd + 1 这两行代码
Case 3
线性建树
- Splay：直接建成一条链
- Treap 法一：先建成完全二叉树，对每个节点递归回来时若优先级不对就向下旋，线性时间和正确性不难证明
- Treap 法二：用栈存可能成父亲节点和右儿子的点（即最右链），这个方法同样可以应用于后缀树、笛卡尔树等的建树中
Case 4
无旋平衡树（FHQ-Treap、替罪羊树）的进阶应用
- 由于其不旋转的性质，它是可以用于嵌套数据结构中的外层嵌套的平衡树以及优化 dp（OI Wiki 上怎么现在还没有“平衡树套线段树”内容啊 qwq）
- 支持可持久化
Case 5
旋式 Treap 的断树 & 并树
-
断树：记优先值为 \(heap\) 值
-
并树：相信方法你自己也能编出来好几种
有什么用？
- Splay 在可持久化时：由于均摊，可以被卡（在某个操作代价很大时反复回到前一个版本去算）
- Treap 由于随机，期望时间复杂度是对的，常数小、不被卡
Case 6
非递归平衡树写法
举例：Splay 也有递归、非递归的写法，比如 OI Wiki 中的 Splay 就是非递归写法
优点：常数小、代码量与递归版差不多、清晰易调
两种写法：
-
记父亲的写法
此写法逻辑相对清晰，但代码长度相对大；但是支持中途查找（LCT 要用到）
-
栈，把不断找儿子的栈存下来，临时记了一串父亲
此写法据说更快，代码短，但是不支持中途查找