fhq_treap（无旋 treap） 参考：远航之曲的博客。 感觉比较意识流。 核心思想是平衡树分裂和合并。 类似于 Splay 把区间分离出来，fhq_treap 可以把平衡树进行分裂来提取需要的区间，再通过合并平衡树来维持树高（即堆性质）。这样不仅可以做到维护区间，还免去了旋转操作，代码较为简单。 split & merge &…

也只有我这种蒟蒻会现在才学平衡树吧…… 本博客参考：PoPoQQQ 和 nzhtl1477 的课件；do_while_true, hzwer, 皎月半洒花 和 yybyyb 的代码启发 其实“参考”也就是我本人在学习时使用的资料。 前置 - 二叉搜索树（BST） 模板题：Luogu5076 关键性质：一个节点 $x$ 左子树所有点的关键字都比 $x…