课前零食：从排好队到会分身的树

这一份零食专门给 FHQ Treap 准备。正式课一开口就是 split/merge，确实像有人把你带到乐高城堡前，只递来两块奇形零件说“拼吧”。今天我们从最笨的队伍开始，一块一块看它们为什么会出现。

本节目标

学完后，你能：

比较无序数组、有序数组、普通 BST 在动态有序集合上的优缺点；
同时说出 Treap 的 BST 键值不变量和随机优先级堆不变量；
从“按键切开”和“把两段接回去”的需求发明 split 与 merge；
手动追踪 pull、按值 split、merge、插入、删除一个重复值和第 $k$ 小；
知道 FHQ Treap 给的是期望 $O(\log n)$，而非无条件的最坏界。

前置知识与课前自测

前置：数组、二分查找、递归、二叉树、随机数的基本直觉。

排好序的数组中查一个值很快，为什么在中间插入一个新值仍可能慢？
把递增键依次插入普通 BST，会长成什么形状？
一个节点若知道左右子树分别有多少元素，怎样判断第 $k$ 小在左、自己还是右？

答案

1. 后面元素都要整体右移，最坏 $O(n)$。2. 一条链，查找和插入退化到 $O(n)$。3. 设左子树大小为 `L`、本节点重复数为 `cnt`：$k\le L$ 去左；$L

互动规则：今天先别急着相信树

这节要用同一组数反复做实验：

$$ S=[4,2,7,5,2]. $$

请在纸上画四栏：结构里存了什么、本次操作看了/搬了哪些元素、操作后仍必须成立的性质、下一步还缺什么。每读到“停顿”时先停下来；不要把折叠区当成自动播放按钮。

我们的贯穿任务是依次执行：插入 6、删除一个 2、求 rank(6)、求第 3 小。它们不是题目，而是用来观察结构是否真的在工作。你要反复问自己：我现在维护的是一串数、一个顺序，还是一棵带摘要的树？

从零搭框架：先把人脑会做的事拆开

第 0 步：把“有序集合”翻译成四种动作

先不许说 Treap，也不许说 split。对一个能重复的整数集合，写下下面四句话各自真正需要的信息：

动作	人脑最直接的做法	若没有顺序，最先卡在哪
`insert(x)`	把 `x` 放进某个容器	放哪儿才能仍有序？
`erase_one(x)`	找到一个 `x` 并删掉	怎么确认只删一个？
`rank(x)`	数有多少数严格小于 `x`	要把所有数都看一遍吗？
`kth(k)`	排序后取第 `k` 格	每次都重新排序吗？

停顿 0：在 $S$ 中执行 rank(6)。请先圈出严格小于 6 的元素，并写下你看了几张“数卡”。

展开：最暴力账本

小于 6 的是 `4,2,5,2`，所以排名是 5（排名从 1 开始）。无序数组必须看 5 张卡；求第 3 小还要排序或反复找最小值。这里的第一个瓶颈不是“不会比较”，而是每次询问都把同一批大小关系重算了。

第 1 步：先试两种数组，让代价亲自出现

无序数组把 6 直接追加，几乎不用移动；但 rank(6) 和 kth(3) 都要重新认识全体成员。有序数组先把 $S$ 写成：

下标:  1  2  3  4  5
数值:  2  2  4  5  7

现在插入 6。请在纸上画一个空格，并用箭头表示谁要右移。

停顿 1：二分能很快找到 6 应在 5 和 7 之间。那为什么插入仍不是对数复杂度？这一步到底移动了哪几格？

展开：找到位置不等于完成插入

`6` 应放在第 5 格，原来的 `7` 必须从第 5 格搬到第 6 格。这个例子只搬 1 个元素；若插入最小值，后面所有元素都要右移。二分查找只解决“问哪里”，没有解决“给它腾位置”。数组实验给出第一个设计要求：**希望保留有序性，同时插入/删除只改少数局部连接，而不是搬一大段连续内存。**

第 2 步：把“左边更小、右边更大”画成路口

二叉搜索树（Binary Search Tree, BST）把一个数放在节点上。对键 4，小于它的数永远向左，大于它的数永远向右；相同键先暂时记在同一张卡的 count 里。请按顺序插入 4,2,7,5,2，每一步只回答两个问题：

比较当前键后，下一步只能去左还是只能去右？
到空位置或相同键时，哪一项局部信息要改变？

建议把每个节点画成卡片：

key = 4     count = 1
left = ?    right = ?

停顿 2：在你画出的 BST 中，找 6 会经过哪些键？插入第二个 2 时，为什么“另建一个同键节点”和“把 count 加一”都可行，但后续规则必须统一？

展开：BST 已经省掉了什么

找 `6` 会经过 `4→7→5`，最后落在 `5` 的右侧。BST 每次比较都能排除一整侧子树，所以若树矮，操作只需走一条根到叶路径。重复值若合并成 `count`，`size` 必须把 `count` 全算进去；若分开建节点，则每个节点贡献 1。两种账本都能用，混用时第 $k$ 小必错。

第 3 步：请你亲手把 BST 攻击成一条链

重新从空树依次插入 1,2,3,4,5,6。不要跳步，画出每条新边。然后在表中填写：

插入到	需要比较几次	新节点深度	树高
1	0	0	0
2
3
6

停顿 3：这棵树和有序数组的“从左走到右”相比，真的躲开线性代价了吗？若想修复它，绝不能破坏哪一件事？

展开：新的账本要求

它变成向右的链；插入第 6 个数要比较 5 次，高度也是 5。我们必须保住 BST 的键值顺序，否则排名与二分路线都没了；但还要让“谁更靠近根”不再由输入先后顺序独裁。于是需要第二把、与键无关的尺子来决定树形。

第 4 步：给每张键卡发一张随机优先级卡

现在用下面这组固定优先级做纸上实验，先别把它当随机数：

键 `key`	2	4	5	7
优先级 `priority`	35	60	83	20

约定“大优先级在上”。请先回答：最高优先级是谁？它的左边只能放哪些键，右边只能放哪些键？然后在左右两边重复同样问题。

停顿 4：不看下方答案，画出整棵树，并在每条边旁写两句证词：一条关于键大小，一条关于优先级大小。

展开：两条不变量第一次同时落地

根是 `5/83`。左侧键为 `2,4`，其中优先级更高的 `4/60` 做左孩子，`2/35` 是它的左孩子；右侧是 `7/20`。中序读出 `2,4,5,7`，所以键值有序；每个父亲优先级更大，所以满足堆序。这不是“先按优先级排序再插入”的技巧，而是同时维护两条不变量：键决定中序，优先级决定根。随机发优先级时，递增键也不再必然做成一条链。

第 5 步：没有 `split` 时，插入到底在重复做什么

想把 6 放进刚才的树。你当然可以沿 5→7 找位置，再想办法让优先级关系恢复；但请换一种描述：我们真正想要的是把旧集合切成“比 6 小”“等于 6”“比 6 大”三堆，处理中间那堆，再按原顺序接回去。

这句话就是 FHQ Treap 的框架，不是代码技巧：

输入集合
    ↓ 按一个边界切开
几块各自仍合法的树
    ↓ 只处理目标块
按键范围正确地接回

停顿 5：对边界 x=4，把上一步的树切成两棵。根 5 应去左树还是右树？既然根去右树，哪一侧子树完全不用递归？

展开：这正是 split 的递归方向

`5>4`，所以根和它的右子树（键都大于 5）一定属于右树；只有左子树可能混有 `≤4` 和 `>4` 的键，才需继续切。到 `4` 时，`4≤4`，它和左子树整体进入左树，继续切它的右子树。递归只沿一条可能跨边界的路径走。

问题动机：队伍既要有序，又要经常插队

动态有序多重集常问：插入/删除一个数、某数排名、第 $k$ 小、前驱后继。三个朴素选项各有一处疼：

结构	擅长	动态时的瓶颈
无序数组	末尾插入	排名、第 $k$ 小要扫描/排序
有序数组	二分、按下标取数	中间插删要搬很多元素
普通 BST	按键走左/右	恶意或递增插入会变成链

我们希望像 BST 一样按键找位置，又希望树高不会总被输入顺序欺负。Treap 的做法非常俏皮：键 key 决定中序顺序，另发一张独立随机的优先级 priority 决定谁更靠近根。键管排队，优先级管谁坐树顶；两位领导分工，不抢麦。

步步式引导

1. 两条不变量如何同时存在

Treap 同时满足：

BST 不变量：左子树键不大于当前键，右子树键不小于当前键（重复值的精确约定必须全程统一）；
堆不变量：本讲取“大优先级在上”，父亲 priority 大于等于孩子。

给每个键独立随机优先级后，键的中序顺序固定，树形等同于这些键按优先级建出的笛卡尔树（Cartesian tree）。随机优先级让任一键出现在很深位置的概率很小，所以树高与随机 BST 同阶，期望 $O(\log n)$。

这里“随机”只影响复杂度，不影响集合内容正确性。若随机源很差或面对能预测优先级的对手，树仍可能长歪；别把“期望”听成“永远不会翻车”。

2. 发明 `split`：按键把一棵树变成两棵

设 split(root, x) 返回 (a,b)，其中 a 所有键 <=x，b 所有键 >x。观察根：

若 root.key<=x，根和左子树必在 a；只需继续切右子树，把切出的左半接回 root.right；

否则根和右子树必在 b；只需继续切左子树，把切出的右半接回 root.left。

split(root, x):
if root is null: return (null, null)
if root.key <= x:
    (middle, right) = split(root.right, x)
    root.right = middle
    pull(root)
    return (root, right)
else:
    (left, middle) = split(root.left, x)
    root.left = middle
    pull(root)
    return (left, root)

你没有“重建”任何树，只改递归路径上的一条孩子指针。其余子树原封不动，BST 和堆性质仍成立。

3. 发明 `merge`：已排好前后关系的两棵树接回去

merge(a,b) 的前提是：a 所有键都不大于 b 所有键。谁应做根？优先级更高者。若 a 的根优先级更高，a.left 不动，只需把 a.right 和 b 继续合并；否则对称处理。

merge(a, b):
    if a is null: return b
    if b is null: return a
    if a.priority > b.priority:
        a.right = merge(a.right, b)
        pull(a)
        return a
    else:
        b.left = merge(a, b.left)
        pull(b)
        return b

pull(node):
    node.size = size(node.left) + node.count + size(node.right)

pull 每次孩子变动后立刻重算。它很朴素，却是排名和第 $k$ 小不会悄悄坏掉的账房先生。

4. 所有操作都变成“切、处理、接”

为了清晰处理重复值，这里令一个节点有 count 个相同键。插入/删除键 $x$ 时，先切出 <x、=x、>x 三块：

(less, at_least) = split(root, x - 1)
(equal, greater) = split(at_least, x)

insert x:  equal.count += 1, or equal = new_node(x)
erase one x: if equal exists: equal.count -= 1; remove it if count becomes 0
root = merge(less, merge(equal, greater))

正式课会采用“重复值各建一个节点”的统一写法；两种方案都可以，但不要把 count 的 size 公式和“每个节点只算 1”混在一起。

纸上模拟：把“切、处理、接”写成可检查的流水线

下面不许只在脑中说“切一下”。仍从中序多重集 [2,2,4,5,7] 开始，执行 insert(6)。每一格先自己填，再核对。

阶段	你应写下的键集合	这一阶段允许改什么	需要保持什么
初始		无	中序有序、每个 `size` 正确
`split(root,5)`	`less` / `at_least`	递归路径的孩子指针	`less≤5<at_least`
`split(at_least,6)`	`equal` / `greater`	同上	`equal=6`，其余大于 6
新建节点		`count` 或新节点	新节点是合法单点 Treap
两次 `merge`		连接边与 `pull`	左树键范围不越过右树

展开：插入 6 的完整账本

第一次切后 `less=[2,2,4,5]`、`at_least=[7]`；第二次切后 `equal=[]`、`greater=[7]`。新建 `6` 后，先合并 `6` 与 `[7]`，再合并 `[2,2,4,5]` 与结果。无论优先级使根具体长成什么样，中序必须是 `[2,2,4,5,6,7]`。每一处孩子指针改变后都调 `pull`，否则某个祖先仍误以为子树只有旧大小。

接着从 [2,2,4,5,6,7] 删除一个 2，并求第 3 小。请把这两个问题拆开：

删除一个 2 时，三次切分后的 equal 里应有多少个元素？count 从几变成几？
假设当前根为 5，左子树元素数为 3；第 3 小首先向哪边走？再假设左孩子为 4、它左子树大小为 2，第 3 小落在哪里？

展开：别跳过 size 的含义

`equal` 是一张 `key=2,count=2` 的卡；删一个后变成 `count=1`，不是把整张卡丢掉。第 3 小在根 `5` 处满足 $3\le left\_size$，先去左；在 `4` 处满足 $left\_size+1=3$，答案为 4。每次走向一侧，都是依据已被 `pull` 维护的“这一整块有多少元素”。

核心知识：每次递归都在维护哪些账

split 的返回值满足键范围分界；merge 的输入满足整体键序；二者只让高优先级根处在上方，因此保留堆序。每次改孩子后 pull，所以 size 始终等于子树元素总数。于是沿 left_size 走第 $k$ 小时，丢弃的元素数恰好正确，不会漏也不会重。

每个基本操作只沿一条期望对数高的递归路径走，故插入、删除、排名和第 $k$ 小期望 $O(\log n)$，空间 $O(n)$。若题目要求严格最坏 $O(\log n)$，要看红黑树、AVL 等确定性结构；FHQ Treap 不假装有这张证书。

实现指南

统一 split 边界：本篇是左边 <=x、右边 >x。若改成 <x/>=x，所有插删公式都要一起改。
节点编号/指针为 0 或 None 时，size(空)=0；每次改完 left/right 后再 pull。
随机优先级应使用质量较好的、独立的生成器；rand() 低位和固定可预测模式都不理想。
kth(k) 前检查 $1\le k\le size(root)$；递归深度在极端退化时可能危险。
调试时打印中序序列（应有序）和每个节点优先级（父亲应不小于孩子）；两条不变量分开查，定位快很多。

互动小实验室

运行从排好队到会分身的树.py。程序先要求你预测有序数组的搬动和优先级根，再使用固定种子的随机优先级构建同一棵树；因此每次树形一致、便于复盘。启动日志会插入一组小数并打印 split/merge/pull；之后可以输入：

+ x / - x：插入或删除一个整数；
rank x：查询严格小于 x 的元素数加一；
k k：查询第 k 小；
show：打印侧着的树、中序序列和每个节点的 size。

建议先执行 + 6，猜一猜它被切到哪一边；再 - 2 两次，观察重复值的 count 如何影响 size。树会“分身”只是指针改了归属，不会偷偷复制数据，放心玩。

扩展与联系

把 split 的依据从键改成子树大小，就得到下一节的隐式 Treap，可维护序列区间；给节点加 Lazy 标记可支持区间翻转。Splay 用旋转把最近访问点伸到根，适用思想不同；ODT 则依赖输入契约，不能当作平衡树的安全替代品。

总结与自检

merge(a,b) 为什么一定要先保证所有 a 的键不大于所有 b 的键？
split 时为什么只递归到一侧孩子？
pull 若漏调一次，第 $k$ 小为什么可能错误？
随机优先级改变的是正确性还是复杂度保证？

自检答案

否则接回去会破坏 BST 中序；根和一整侧子树的归属已由键比较确定；祖先的 `size` 不再等于真实元素数；它不改变有序集合内容，只影响树高的期望界。

一周预热安排

第 1 天：比较有序数组插入和递增 BST 的形状。
第 2 天：给 4 个键随手发优先级，画出同时满足两条不变量的树。
第 3 天：手做一次 split(root, x)，在每一步标注左右键范围。
第 4 天：手做一次 merge，每次选择优先级更高的根。
第 5 天：运行互动程序并做插删、排名、第 $k$ 小；随后进入FHQ Treap 正式课。

00-课前零食-从排好队到会分身的树.md 17 KB Permalink History Raw