lessons/课程/11-平衡树/01-FHQ-Treap按值分裂与顺序统计.md

FHQ Treap：按值分裂、合并与顺序统计

本节目标

掌握无旋 Treap（FHQ Treap）的两条原语 split/merge，维护动态有序多重集的插入、删除、第 k 小、排名及极值删除。

前置知识与课前自测

前置：BST、随机化、子树大小。

1. split(root,key) 应保证两棵树满足什么键范围？
2. merge(a,b) 需要什么前置条件？
3. 为什么随机优先级能给出期望对数树高？

答案

1. 左树键不大于 key，右树键大于 key（或另一套统一约定）。 2. a 的所有键不大于 b 的所有键。 3. 键确定 BST 中序，独立随机优先级确定笛卡尔树；其期望深度与随机 BST 同阶。

问题动机与核心知识

FHQ Treap 不围绕某节点旋转，而是把所有操作归结为：

• 按键/排名切成两棵合法 Treap；
• 在键域有序前提下，按随机优先级合并。

节点同时满足键的 BST 顺序和随机优先级的堆顺序。size 在每次改儿子后 pull。重复值可每次建独立节点，也可存 count；附件前者更统一。

实现指南

• 随机数使用固定高质量生成器，避免 rand() 低位和对抗数据。
• 删除一个值时切成 <x、==x、>x，只删等值树一个节点。
• 递归期望深度对数，但随机性失效仍可能退化；这也是它与保证最坏界结构的差别。
• kth 前确认 $1\le k\le size(root)$。

精选例题 1：Black Box

来源与题意

• POJ-1442 Black Box，Northeastern Europe 1996
• 依次插入给定序列；第 i 次询问发生在已插入前 $u_i$ 个数后，输出当前第 i 小。

Hint 1

询问位置单调，继续插入到 $u_i$ 即可。

Hint 2

Treap 的子树大小支持第 k 小。

Observations、Editorial 与证明

时间轴只前进、不删除，所以在每次询问前补插新元素，然后沿 left_size 选择第 i 小。Treap 中序序列始终是当前多重集排序结果；kth 根据左子树元素数排除整棵子树，归纳能到达排序序列第 k 项。期望复杂度 $O((M+N)\log M)$。

核心伪代码与附件

for query_index i in 1..Q:
    while inserted < u[i]: root = insert(root, next_value)
    output kth(root, i)

完整 C++17 附件

精选例题 2：Double Queue

来源与题意

• POJ-3481 Double Queue，Southeastern Europe 2007
• 动态加入 (客户编号,优先级)，支持弹出最高优先级或最低优先级客户；空时输出 0。

Hint 1

以优先级为 BST 键，节点附带客户编号。

Hint 2

最小/最大分别是最左/最右节点，输出后按键删除。

Observations

• 队列名称不重要，操作集合决定它是有序集合。
• 极值查询可沿单链完成，不需维护额外 min/max。
• 删除后必须重新合并被切开的左右树，保持所有权唯一。

Editorial 与正确性证明

插入时按优先级分裂并夹入新节点。删除极值先找到键，再把 <key、==key、>key 分开，丢弃等值根并合并其子树后接回。分裂/合并保持中序键序与优先级堆序，所以每步后仍是合法 Treap；中序极端节点正是优先级极值。每操作期望 $O(\log n)$。

核心伪代码与附件

insert(id, priority): split by priority; merge(left, new_node, right)
pop_min/max:
    find extreme node by left/right pointers
    output its id
    erase one node with that priority via splits and merges

完整 C++17 附件

扩展与联系

FHQ Treap 可按键持久化：split/merge 时路径复制；也可按排名成为隐式序列树，见下一节。若要求严格最坏 $O(\log n)$，需红黑树、AVL 等确定性结构。

总结与自检

1. split 与 merge 的前后条件是什么？
2. 重复值删除一个时如何切分？
3. kth 怎样利用左子树大小？
4. 随机优先级影响正确性还是只影响复杂度？

课后训练建议

与 multiset 随机对拍插删、排名、kth。主动插入递增键检查树高分布；固定随机种子便于复现失败。