“分数发生变化后，立即显示新的名次”还不是一个足以实现和分析的需求。相同分数是否并列，删除之后名次是否连续，查询不存在的记录应返回什么，都能改变程序的合法输出。先固定这些选择，才能讨论哈希表、数组和有序树各自承担的工作。

本系列从一个本地动态榜单开始。它没有网络请求、权限和并发更新，全部操作顺序执行。首篇只建立操作契约与朴素参照；后续结构必须回答相同的问题，才能比较成本。MIT 的算法导论讲义把问题表述为输入与允许输出之间的关系，这也是这里区分“需求”和“某一种程序”的依据。MIT 6.006 Lecture 1

同分记录怎样排序

每条记录包含整数标识 id 和整数分数 score。标识从 0 开始，由插入操作单调分配，删除后不复用。分数可为负数，同分合法。排序键统一写为 (-score, id)，按字典序升序比较，因此高分靠前，同分时较早分配的 ID 靠前。

ID	分数	排序键	名次
0	80	(-80, 0)	2
1	95	(-95, 1)	1
2	80	(-80, 2)	3

把 ID 2 更新为 100，顺序就成为 2, 1, 0。再把 ID 0 更新为 95，ID 0 排在 ID 1 前面；打破同分的是记录标识，更新时刻不参与排序。若采用“最后更新者优先”，就必须另外保存时间或序号，不能继续用当前接口的证明。

这里的名次是严格顺序位置 1, 2, 3。比赛中常见的并列排名 1, 2, 2, 4 属于另一套语义。“第 2 名”在那套语义下可能对应多条记录，所以不能把两种名次混在一个返回单条记录的接口里。

操作与边界

设当前有效记录数为 $n$ ，整个操作序列长度为 $q$ 。每次调用观察调用前的完整状态，修改成功后再进入下一次调用。返回一条记录时使用 (id, score)，不返回内部可变对象。

操作	输入与输出	空集或非法边界
`insert(score)`	新建记录并返回新 ID	空集允许插入
`get(id)` / `update(id, score)`	读取分数 / 替换已有分数	缺失 ID 抛 `KeyError`，更新不暗中插入
`delete(id)`	存在则删除并返回 `True`	不存在返回 `False`
`rank(id)`	返回该记录从 1 开始的名次	缺失 ID 抛 `KeyError`
`select(k)` / `topk(k)`	返回第 k 条 / 前 k 条记录	select 要求 $1\le k\le n$ ，否则 `IndexError`；topk 的负 k 抛 `ValueError`，0 返回空表，超过 n 时截断

rank 的输入是 ID，select 的输入是位置。查询分数 80 不能代替查询 ID 0，因为分数可以重复。topk 返回按榜单次序排列的独立列表，实际输出长度记为 $r=\min(k,n)$ ，只讨论合法的非负 k。

记录 ID 的最大值未必接近当前 n。插入百万条再删至一条，存量虽小，下一次 ID 仍继续增长；分析位长时还需要操作总量 q。后续范围聚合按记录 ID 定义区间，也将沿用这个不复用约定。

一个可以逐项核对的序列

先手算，再运行代码，避免把程序自己生成的答案当作参照。下表包含 12 次调用，状态栏只列出操作后的榜单 ID 顺序。

次序	调用	返回或结果	状态
1	`topk(3)`	`[]`	`[]`
2	`insert(80)`	`0`	`[0]`
3	`insert(95)`	`1`	`[1,0]`
4	`insert(80)`	`2`	`[1,0,2]`
5	`rank(2)`	`3`	`[1,0,2]`
6	`select(2)`	`(0,80)`	`[1,0,2]`
7	`update(2,100)`	无返回值	`[2,1,0]`
8	`get(2)`	`100`	`[2,1,0]`
9	`delete(1)`	`True`	`[2,0]`
10	`delete(1)`	`False`	`[2,0]`
11	`insert(-5)`	`3`	`[2,0,3]`
12	`topk(9)`	`[(2,100),(0,80),(3,-5)]`	`[2,0,3]`

另行检查 select(0)、空表上的 select(1)、缺失 ID 的读取和负 k。正常用例中从未出现异常，不等于异常语义已经覆盖。尤其是 Python 列表允许负索引，直接使用 ordered[k-1] 会把 select(0) 错当成最后一名。

先得到正确答案

朴素实现把 id → score 放入字典。每次需要顺序时，将全部记录按 (-score,id) 排序。select 读取下标 k-1，topk 取前缀。rank 也可以排序后定位，但教学参照采用另一条公式：

\operatorname{rank}(x)=1+\left|\{y:\operatorname{key}(y)<\operatorname{key}(x)\}\right|.

两个实现途径使用同一数学定义，却走不同控制流程。比较树将来把“前面有多少条”存成子树大小时，仍然可以用逐项计数检查，不必再用另一棵树验证它。

正确性可以按操作序列长度归纳。空字典恰好表示空榜单。插入分配从未使用的 ID，所以不会覆盖旧记录；更新只改变指定记录的分数；删除只移除指定 ID。每次修改都维持“字典与有效记录一一对应”。整数上的字典序为全序，不同 ID 保证不同记录的排序键不同，因此排序恰有一个确定顺序。位置读取和前驱计数便给出契约要求的 select 与 rank。

终止性来自每次只处理有限字典与有限数组。这个论证不依赖分数的具体分布；运行 12 条操作则只是核对实现是否遵守论证中的状态变换。一般正确性证明与有限运行证据承担不同责任。

教学程序位于仓库 examples/advanced-algorithms/reference_board.py。在仓库根目录运行：

1	`python3 examples/advanced-algorithms/check_foundations.py`

该命令还运行后续基础篇的检查。完整源代码和执行环境见本地仓库 examples/advanced-algorithms/README.md；本批未推送，因此不提供指向尚未发布代码的远程链接。本文配套契约与检查说明可直接下载。

成本必须对应实际操作

先采用单位成本比较模型：比较两个分数和 ID、移动一条记录的引用各计一次基本操作。不把排序当作一步。哈希点查暂按“散列分布与负载因子满足第 04 篇条件时的期望常数成本”处理；最坏碰撞仍可能让一次字典访问扫描线性数量记录。

方案	get	insert / update / delete	rank	select	topk	有效存储
字典加临时排序；rank 单独计数	期望 O(1)	期望摊还 O(1)	O(n) 次比较，另加点查	O(n log n) 上界	O(n log n+r) 上界	O(n)，排序另需 O(n)
字典加连续有序数组	期望 O(1)	最坏 O(n) 移动，外加字典成本	O(log n) 比较，外加点查	O(1)	$O(r)$	O(n)

表内是抽象成本：字典维持紧凑的有效记录存储，枚举 n 条记录花 O(n)，每条记录占常数个字。空间列统计逻辑存储，未声明 CPython 字典删除后会自动缩小底层分配。当前 Python 参照程序的物理容量与枚举开销可能受历史峰值影响，不能仅凭现存 n 推断进程内存；若研究这种行为，应另记底层容量或历史峰值并实际测量。表内排序上界针对比较排序；n 为 0 或 1 时按常数边界单独处理。第二种方案更新分数后，要删除旧排序键，再插入新键。二分只找到了插入位置，位置之后的元素仍要移动。Python 官方 bisect 文档也明确区分了对数查找与线性插入。bisect 性能说明

有序数组的 rank 通过读取该 ID 的分数、构造唯一键，再二分查找。只保存“每个 ID 当前下标”的字典不会自动改善更新：一次头部插入让后面几乎所有下标改变，维护它们仍需线性工作。

若 q 次操作中有 u 次更新、s 次 select 查询，每次查询时规模约为 n，临时排序方案的相关成本可写成 $O(u+s n\log n)$ ，有序数组方案约为 $O(un+s)$ ，再加上 get、rank 与输出成本。规模固定只是一种简化负载；真实推导应对每次调用时的 $n_i$ 求和。大量更新、偶尔读取与大量读取、偶尔更新，会把成本放在不同位置。

哈希表本身按键定位记录，不维护这里定义的全序。对单个 ID 的快速点查不能推出名次查询快；若没有额外顺序信息，统计前驱仍要查看其他记录。第 06 篇才会引入同时保存顺序和子树计数的结构。

怎样判断两个实现回答同一个问题

假设一个实现只保存分数集合 {80,95}，另一个保存三条记录 (0,80),(1,95),(2,80)。它们查询最大分数都返回 95，却无法共用第 k 名的正确性结论：第一个实现已经丢掉了重复记录。最大值样例通过不能证明榜单契约通过，检查必须包含所有会影响输出的信息。

删除的幂等性也需要精确理解。连续删除 ID 1，状态在第一次后就不再变化，但返回值分别是 True 与 False。若仅比较最终状态，会漏掉第二次调用的错误返回值。相反，插入不是幂等操作：两次插入相同分数必须得到不同 ID，留下两条记录。后续的差分检查会同时比较返回值和完整状态。

更新是替换分数，不是增加分数。把 update(2,100) 当成“加 100”会得到 180，名次在当前小例中恰好仍然是第一，只有读取分数或查询另一个合适阈值才能揭露差异。这说明反例的设计应针对契约的每个可观察量，而不是只看最醒目的排名结果。

程序也不提供历史快照。调用者拿到 topk 的列表后再更新榜单，旧列表保留原来的整数对，但这只是一次查询结果，不能据此查询未包含的历史记录。完整历史聚合要等第 14、36 篇建立版本语义；当前接口不预留一个没有实现的“版本号”参数。

这些区分可以转化为比较候选实现的准则：输入合法域相同，操作副作用相同，返回值与异常相同，再比较成本。只要其中一项不同，就需要先解释需求变化，不能把更少的工作直接称为同一问题的优化。

模型失效时需要补哪个变量

当分数和 ID 都能放进一个机器字，word-RAM 可以把相应算术与比较视为常数成本。字长 w 至少要足以寻址内存。Python 整数没有这个固定宽度保证：若分数含 L 位，求负、散列和比较的成本会受 L 影响。用一万位整数的运行时间说明“基本操作一定是常数”不符合模型。

将 ID 换成长字符串也会增加比较成本，两个名字可能共享很长前缀。此时可保守地把一次比较的最坏字符工作记为 O(L)，并检查预计算排序键是否已经计入成本。不能只把元素个数 n 写在横轴上，就认为所有输入等价。

本例选择整数分数，排除了浮点 NaN。NaN 的比较不满足通常的全序直觉，若随意允许它进入排序键，上面的唯一顺序论证就缺少前提。修补方式是先定义输入规则，而不是等排序出现奇怪结果再猜解释器行为。

输出也是工作。返回前 k 条至少要产生 r 条结果，在逐条输出模型下有 $\Omega(r)$ 成本。“Top-k 对数时间”若省略 r，就只能指找到边界或返回一个未物化的视图，不能指当前接口返回的完整列表。

先修自测与练习

先修自测包含六个短问题。先求二分 [1,1,3] 中第一个 1 的位置，再计算一棵 5 节点树的遍历访问次数，解释无权图 BFS 的分层顺序。数学部分求 $1+2+\cdots+2^t$ ，写出插入保持 ID 唯一的归纳步骤，并说明固定哈希函数后为什么不能继续“对随机函数取期望”。

参考思路分别是：半开区间左边界；每个节点一次，但栈深取决于树高；队列按路径长度分层；几何级数 $2^{t+1}-1$ ；新 ID 大于所有曾分配 ID；概率空间必须先明确。前两项对应第 01 篇，求和对应第 02 篇，最后一项在第 04 篇展开。BFS 的队列不变量若还无法解释，应先补图遍历基础。

将同分顺序改成“更新越晚越靠前”。给出额外状态、两条能够区分新旧契约的操作序列，并说明 rank 与 select 的互逆性质是否仍成立。提示：先决定一次读取是否算更新，以及计数器何时增加。
实现有序数组方案，复用本文 12 条操作和异常检查。对一次头部插入统计移动元素数，比较 $n=8,16,32$ ；不能仅报告二分比较次数。再写一个查询远多于更新的负载，解释为什么它可能适合有序数组。

参考资料

MIT 6.006 Lecture 1：问题、正确性与计算模型，第 1–3 页。榜单 API 是本系列自行定义的教学契约。
Python bisect 文档，插入点语义与性能说明；不把它当作 Python 字典最坏复杂度的依据。