不持续更新。
前置知识
二叉搜索树
堆
FHQ-Treap 一般使用小根堆。
FHQ-Treap
简述
FHQ-Treap 是一种基于分裂和合并操作的平衡树。它没有旋转，极易上手，非常适合 cainiaoshanglu。
核心思想
我们对于一个点存储两个权值 \(a_i, h_i\), 其中 \(a_i\) 满足小根堆性质, \(h_i\) 满足 BST 的性质. 我们可以对于 \(h_i\) 进行随机赋值, 使得期望时间复杂度为 \(\mathcal{O}(\log{n})\) 的.
FHQ-Treap 基于合并与分裂函数, 轻易的实现了 P3369 的六种功能, 即易懂又他妈的好写.
\(\text{Merge}\)
满足 \(h_i\) 来合并.
假设现在两棵树合并到 \(x, y\). 若当前
标签：BST,合并,Treap,小根堆,平衡,FHQ From： https://www.cnblogs.com/aemmprty/p/18104830