同一份记录可以按分数排名，也可以按记录编号查询区间总分。这是两种顺序：排名位置会随分数改变，记录编号却不能跟着移动。再加入历史查询，就必须说明每个结果属于哪个版本。

本篇组合06篇的AVL顺序统计树与14篇的持久化区间和，沿用00篇的记录接口。当前排名可以更新，历史只查询按编号划分的范围总分，不承诺历史排名，也不把本地单线程程序称为完整多索引MVCC系统。

身份、排序与范围各用什么键

构造时指定非负容量C，表示整个运行最多创建C条记录。记录ID从0开始单调增加，删除后不复用；达到C次插入后，即使当前记录很少，也拒绝继续插入。这个固定上限来自所复用的持久化树定义域，不代表动态榜单必须天然拥有固定容量。

当前记录由字典保存id到score的映射，score为整数，允许负分和重复分数。AVL中的键为(-score,id)，所以高分靠前，同分时较小ID靠前；唯一ID让不同记录不会因分数相同被合并。

区间聚合使用记录ID，不使用排名。sum(l,r)表示所有仍存在且满足l≤id<r的记录分数之和，合法边界为0≤l≤r≤C。尚未分配或已经删除的位置贡献0，空区间返回0。

例如ID0分数10、ID1分数20，排名顺序为1、0，但sum(0,1)是10。把数组下标误当成当前名次，会在更新分数后查询另一个集合；换用更快的数据结构并不能修复这个接口错误。

哪些操作产生新版本

初始版本为0，没有记录，所有范围和为0。每次成功插入、更新或删除已有记录都产生一个新版本，版本号递增1。把分数更新为相同值也产生版本；删除不存在的ID返回False，不产生版本。查询不会推进版本。

插入返回新ID；更新保持00篇的None返回值，删除返回布尔值。get和rank遇到缺失ID抛KeyError；select(k)从1开始，越界抛IndexError；topk(0)返回空，k大于记录数时截断，负k拒绝。调用者可读取version了解最后一次成功变更编号。

sum(l,r,version=v)在v版本的根上查询。范围仍取固定ID域[0,C)，不是“该版本已创建记录数”；因此可以询问一个尚未创建的未来ID位置，它在旧版本中贡献0。版本越界拒绝，而不是悄悄改查最新状态。

历史只有总分，没有历史存活标记。分数为0的已存在记录和不存在记录在单点历史和上都返回0，不能据此推断历史身份是否存在。若业务需要历史存在性，应另建相同版本的计数或标记索引，本篇没有这个接口。

一次修改怎样更新三个视图

插入分数s时，先确认ID容量未耗尽，再把(id,s)放入当前字典、把(-s,id)放入AVL，并把持久化数组的该位置从0增加到s。更新已有记录从old改为new时，删除AVL旧键、加入新键，同时在最新持久化根上增加new−old。

删除已有记录时，去掉字典项与AVL键，并在对应数组位置增加-score，使新版本中的贡献变为0。过去版本根未被修改，仍能看到删除前的分数。

这三种操作都从同一个最新状态出发，不允许只更新排名树而保留旧聚合根。所有普通输入边界在变更前检查，方法正常返回时三个当前视图对应同一个版本。

这是单线程、无并发查询插入修改中途的教学契约。它不保证内存分配失败时回滚全部结构，也没有持久化日志或崩溃恢复。如果把代码放进并发服务，不能只给版本号加一把锁，就声称整个多索引更新已原子提交。

正确性可以按版本归纳

维护三个不变量：字典恰好表示当前存活记录；AVL恰好包含这些记录的(-score,id)键；最新区间树每个ID叶子等于当前分数，缺失记录为0。

版本0显然满足。对插入，新的ID此前从未使用，新增键与叶子不会覆盖另一个记录；对更新，旧键被新键替换，叶子加差值后等于new；对删除，唯一键被移除，叶子加负旧分后为0。因此每次合法修改保持三个不变量。

当前排名由AVL中严格小于(-score,id)的键数加1得到，正好适配00篇的一基rank。select返回第k个键，再把(-score,id)转换回(id,score)。排名与选取互逆不依赖分数互异，只依赖复合键唯一。

历史正确性沿用14篇的路径复制：只创建被修改根到叶路径上的节点，未修改子树共享；旧节点不可变，旧根代表的数组永远不变。这里每次只从最新根生成下一版本，虽然底层PersistentSum允许从任意旧根分叉，榜单接口并未开放分叉写入。

组合后的成本不能只写一个log n

记当前存活记录数为a、总成功变更数为q，固定容量为C。构造零值聚合树需要O(C)时间与节点。AVL更新O(log(a+1))，持久化点更新O(log(C+1))，二者参数不同；删除很多记录不会缩小已经建立的ID宇宙。

每次修改的树上工作合计O(log(a+1)+log(C+1))。根列表追加有摊还成本，字典操作按期望常数成本计，整数比较与算术还有位长成本。因此不能把整段Python方法称为无条件最坏对数延迟。

当前rank/select树上查询O(log(a+1))；范围和及历史范围和O(log(C+1))，get按字典期望常数分析。若topk通过重复select实现，返回t=min(k,a)条需要O(t log(a+1))树上工作，不能借用未实现的中序迭代器声称O(log a+t)。

保留全部版本需要O(C+q log(C+1)+q+a)级别的节点、根引用及当前索引空间，另外计入Python对象和大整数。零差值更新也复制一条路径，不能把“结果没变”误写成“没分配”。

朴素参照在每次成功变更后复制当前字典，保存完整快照；在紧凑字典抽象下，单次写入成本与当时存活记录数成正比，历史范围和直接遍历所选快照。实际CPython字典还受删除后的历史容量影响，不能只凭当前存活数预测复制或遍历时间。它不共享树结构和增量维护逻辑，适合发现版本错配。

可复跑检查

教学实现位于examples/advanced-algorithms/versioned_board.py，直接复用AVL与PersistentSum；SnapshotBoard使用00篇朴素记录接口和完整字典快照。仓库根目录运行：

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

本次实际输出为status=passed，共108个操作步骤，检查337610次历史范围查询；固定随机种子20260920，随机部分100步，最终版本53、下一个ID为12，非法输入拒绝检查26次。原始结果保存在writing-plans/advanced-algorithms/evidence/versioned-board-results.json。

检查覆盖同分排名、负分、零分、更新为原值、重复删除、空容量、删除后容量仍耗尽，以及所有已生成版本的合法半开范围。每次修改后还核对当前记录、排名、select、topk和AVL不变量。两个实现接收同一操作流，参照结果来自完整快照，不用被测树计算答案。

这些是有限输入的差分检查，不是归纳证明的替代，也没有测量吞吐或并发一致性。当前实现未提供历史排名、版本回收、异常回滚与ID域扩容；这些接口不能从检查通过中推导出来。

练习

依次插入分数5、5，更新ID0为8，再删除ID1。列出每个版本的sum(0,2)和当前排名；指出哪些历史身份问题无法仅靠范围和回答。
容量C=3时反复插入后删除，第三次删除后还能插入第四条吗？解释把ID回收复用会怎样改变旧版本区间的语义。

参考资料

MIT 6.046J Lecture 9: Augmentation：第1–2页的子树字段维护与顺序统计；本文统一使用00篇的一基排名。
Driscoll、Sarnak、Sleator、Tarjan：Making Data Structures Persistent：印刷页87、89的持久化定义，以及116页的路径复制说明。本文采用简单路径复制，不套用其他节点复制技术的空间界。

多视图一致性是本文接口下的归纳结论；上述材料分别支持增广树和持久化结构，并不提供这个Python组合的事务保证。