我勒个范浩强啊

FHQ-Treap定义

• 是无旋Treap
• 用split 和 merge 维护

Treap的简介

• 随机化数据结构
• 二叉搜索树 + 二叉堆（小根大根皆可）
• 用键值维护 给每个键值一个随机附加的优先级，让键值满足二叉查找树的结构，让优先级满足二叉堆的结构。

Treap的原理

• 以随机顺序插入数据构造的二叉搜索树
• 节点插入的顺序是随机的，所以构造的二叉搜索树在概率上趋近平衡。
• 但不能提前知道构造树的数据，所以用于动态算法。

Treap维护

用左旋和右旋维护 小口诀 枢纽拎起来，父兄挂下面，右孩给父亲。

插入

• 插入的过程中通过旋转来维护优先级的堆性质

FHQ-Treap的实现

split

• 将一个FHQ-Treap 按某个值分裂成2个

以权值分裂