守株阁

不断加入无向边后，怎样判断两个顶点是否已经连通？每次重新遍历图能回答问题，但重复处理了大量已经建立的连通关系。并查集只保存连通分量划分。加入一条边时，合并两个端点所在集合即可，不必保留分量内部所有边。 这种压缩也限定了能力。并查集可以证明两个顶点属于同一集合，却不能直接返回连接路径；删去一条边后，也无法仅凭旧划分判断分量是否拆开。本篇只处理固定顶点集合上的合并与连通查询，不把它当成完全动态连通性算法。 森林表示的是什么 初始化输入n个顶点，编号0到n−1，各自构成一个集合。每个顶点保存一个parent指针，根指向自己；沿parent走到的根是当前代表元。根编号只代表集合身份，不承诺是集合最小编号，合并后也可能改变。 接口 语义 DSU(n) n非负；负数抛ValueError find(x) 返回当前代表元；编号越界含负数抛IndexError union(a,b) 合并不同集合时返回True，原已连通返回False connected(a,b) 比较代表元，返回是否同属一组 逻辑不变量是parent边组成森林，且一棵树恰好对应一个集合。初始化显然...

任务进入队列后，优先级可能降低，两个队列也可能合并。只会插入和弹出最小值的堆接口还不足以描述这些操作：怎样定位旧任务、是否允许重复ID、合并后句柄是否仍有效，都会改变实现和成本。 本篇实现可定位元素的二叉最小堆，随后用二项树和势能法解释合并与降键的不同设计。Fibonacci堆采用结构推导，不把一个未实现的高级堆写成实测候选。令n为当前元素数，q为操作序列长度，比较键为 (priority,id)；ID唯一，相同优先级按较小ID先出队。 降键先要找到哪个元素 数组二叉堆只保存优先级时，要修改指定ID需要先扫描O(n)。为消除这次扫描，教学实现增加 pos[id]，记录该元素在数组中的下标。数组元素与位置映射必须互为逆映射；每次交换都同时更新两个位置。 操作 语义 insert(id,priority) 加入元素，重复ID抛ValueError decrease(id,new) 只允许不增的优先级；缺失抛KeyError，增大抛ValueError delete(id) 删除指定元素，返回(priority,id)；缺失抛KeyError pop_min(...

连续查询同一个深层节点时，普通搜索树会反复走同一条长路径。Splay 在访问后把该节点旋转到根，使紧接着的同键查询只检查根。这个局部效果容易观察，但不能由此断言任意访问都很便宜：把一条链的尾节点第一次移到根，本来就需要线性代价。 本篇考虑固定的 n 个不同整数键，只做查找和重排。输入是初始二叉搜索树与 q 次查询；输出是每次是否存在，树内集合始终不变。失败搜索把最后访问到的节点伸展到根，空树直接返回失败。成本先数旋转，再把沿搜索路径的比较计入同阶时间；不在同一个常数公式中混用两种成本。 双旋与连续单旋不同 访问节点x有父亲p和祖父g时，根据三者相对方向选择两次旋转。x与p同为左孩子或同为右孩子是zig-zig，先旋转p与g，再旋转x与p。方向相反是zig-zag，先旋转x与p，再旋转x与g。若x只剩父亲，则执行一次zig结束。 每次旋转保持中序键序，访问节点每轮至少向上移动一层，所以过程终止且集合不变。子树大小按06的孩子依赖顺序重算；实现若保存parent指针，还必须同步祖父到新根、被转移孩子到新父的链接。 不能把zig-zig替换为“总是让x与它当前父亲旋转”。两种过程都可能...

06 篇用每个节点的高度差约束整棵树。如果输入按升序到来，AVL 仍保证对数高度。另一种选择是让树形由算法生成的随机数决定：键负责搜索顺序，随机优先级负责哪个节点在上面。这能得到期望对数代价，但允许某次随机选择产生一条长链。二者的保证不能互换。 本篇实现 Treap 多重集，沿用上一章 add/discard/count/rank/select 的语义；再手算跳表搜索，比较随机化在树形和分层链表中的作用。令 n 为元素总数，d 为不同键数，键比较成本仍按常数计算。重复键增加计数，不重新抽取已有节点的优先级。 两种顺序怎样确定一棵树 Treap 同时满足二叉搜索树键序和优先级最小堆序。优先级互异时，最小优先级的键必须是根；比根小的键属于左子树，比根大的键属于右子树。对子树重复这个论证，整棵树被唯一确定。这也是 Cartesian tree 的一个构造视角。 插入先按键找到空位置，再在新节点优先级小于父节点时旋转上移。旋转不改变中序顺序；旋转后较小优先级节点上移，逐步消除新产生的堆序冲突。每步向根靠近，因此终止。子树 size 仍按06的公式从下向上重算，重复计数不参与优先级比较。 ...

分数更新后，哈希表能迅速找到记录，却不能直接回答新排名。00 篇的参照实现在排名时扫描所有记录，第 k 名查询则重新排序。若查询与更新交替发生，前一次排序结果很快失效。有序树可以沿搜索路径定位分数，再用子树中的元素数量跳过整段候选；树高必须受控，否则有序输入会使路径退化成链。 本篇把这两件事分开证明：AVL 高度约束保证路径短，子树大小保证排名正确。增强字段算错时，树仍可能平衡、搜索仍可能成功，排名却已经错误。因此验证必须同时覆盖键序、高度、平衡和计数。 重复键放在哪里 教学容器是多重集，允许相同键出现多次。每个不同键只占一个节点，节点保存 key、出现次数 count、高度 height、子树元素总数 size 和左右孩子。定义空树高度为 0，叶子为 1；空树大小为 0。令 n 为包含重复项的元素数，d 为不同键数，因此 d≤n。 操作 结果与边界 add(key) 增加一次出现；相同键只增加计数 discard(key) 删除一次出现，成功返回 True，不存在返回 False count(key) 返回出现次数，不存在返回 0 rank(key) ...

一个程序跑得更快，可能只是少算了一部分答案。验证算法实现首先要确认输入输出语义相同，再比较资源成本。第 00–04 篇已经建立契约、不变量、渐近分析、摊还和期望界；本篇把这些结论对应到可复跑检查，形成后续数据结构共同使用的验证方法。 实验输入均由本地程序生成，不使用生产数据。代码只依赖 Python 标准库。正确性检查与计时分开运行：前者遇到不一致应失败，后者记录当前机器上的样本，不负责证明算法对全部输入正确。 独立参照应当独立在哪里 第 00 篇榜单按 (-score,id) 建立全序。直接把优化实现复制一份、改变量名作为参照，很容易保留同一个 bug。更合适的参照是字典保存记录、查询时排序；rank 还可用“严格位于目标之前的记录数加一”逐项计算。 先检查已知答案，再检查关系。12 条手算序列确认同分、更新、删除和 ID 不复用；对每个有效 ID，验证 select(rank(id)) 恰好返回该记录。互逆性质有用，但单独不够：如果 rank 与 select 同时采用了错误的同分顺序，它们仍可能互逆，所以还须与独立排序定义对照。 二分使用标准库 bisect_left 作...

哈希表出现冲突，不代表查找可以返回错误记录。精确字典必须在同一桶中继续比较完整键；随机散列影响的是这一步要检查多少条记录。若要说“期望常数时间”，还需指出随机选择了什么，以及输入是否能观察这个选择。 第 03 篇的摊还分析不需要概率。本篇固定键集，对散列函数的随机选择取期望，再把碰撞成本与扩容成本分开。讨论链式散列，不把开放寻址、密码散列或 Python 字典的内部实现自动归入同一个定理。 先固定概率空间 输入为互异整数键的集合 S，大小 n；桶数 m≥1。每个桶保存完整键值记录，散列值只决定访问哪个桶。插入相同键时覆盖还是拒绝要由字典 API 决定，碰撞分析只统计不同键。 设 H 为一族函数，每个函数把键映到 [0,m)。称它具有本篇所需的通用性，是指任意事先固定的不同键 x、y 都满足： Pr⁡h∼H[h(x)=h(y)]≤1/m.\Pr_{h\sim H}[h(x)=h(y)]\le 1/m. h∼HPr​[h(x)=h(y)]≤1/m. 键集 S 和待查询键必须在 h 随机选定前固定，或至少独立于这次选择。函数选定后，一次运行中的 h 不再变化；期望指重新抽取函数时的成...

一个容量已满的数组追加元素时，可能需要复制全部旧元素。这次操作的线性成本，与一长段追加操作具有线性总成本可以同时成立。摊还分析说明每段合法序列的总账，不要求用户随机操作，也不把昂贵调用的延迟抹掉。 第 02 篇通过求和分析递归，本篇把相同方法用于数据结构的时间序列。讨论对象是抽象动态数组：当前元素数 n、容量 C、操作序列长度 q，C 初始为 1，始终为 2 的幂。只支持末尾追加与删除；中间插删需要移动元素，不属于本篇常数摊还结论。 满时加倍的总复制成本 追加前若 n=C，就分配容量 2C 的存储，复制 n 个已有元素，然后写入新元素。一次普通追加计 1 次写入，一次扩容追加计 n+1 次。这里按存活元素复制收费，未计清零新容量的工作；若分配还需 Θ(C)\Theta(C)Θ(C) 初始化，常数会变化，总阶的论证仍需把它纳入。 从空数组开始连续追加 q 次，复制发生在容量 1、2、4、8 等时刻。设最后一次复制的旧容量为 2t<q2^t<q2t<q，总复制数为： 1+2+⋯+2t=2t+1−1<2q.1+2+\cdots+2^t=2^{t+1}-1&l...

递归程序每层写着两次调用，不意味着总成本就是“层数乘以 n”。子问题有多大、每层共有多少节点、局部工作是否包含复制，都要从实际代码得到。第 01 篇的树聚合已经给出一个反例：左右子树可以很不均衡，遍历时间仍为线性，栈深却可能为线性。 本篇只讨论确定性的最坏成本与比较模型下界。输入规模 n 为元素数，单次比较和引用移动视为单位成本；目标是推导随 n 增长的工作量，不估算墙上时间。下文递推式是被声明的成本模型，不能自动代替任意同名算法的真实实现。 均衡递归的每层账目 对二路均衡归并，设 n 为 2 的幂，边界 T(1)=c0T(1)=c_0T(1)=c0​，每个内部节点的拆分和合并总工作为 cn，c 为正的固定常数： T(n)=2T(n/2)+cn.T(n)=2T(n/2)+cn. T(n)=2T(n/2)+cn. 第 j 层有 2j2^j2j 个子问题，每个大小为 n/2jn/2^jn/2j，所以该层局部工作是 cn。内部层共有 log⁡2n\log_2 nlog2​n 层，叶子 n 个，总成本为 cnlog⁡2n+c0ncn\log_2 n+c_0ncnlog2​n+c0​n，...

二分查找在长度为 1 的数组上出错，通常不是“特殊情况太多”，而是区间含义没有统一。若把循环中的每个变量解释成一个持续成立的命题，空数组、重复值和目标缺失就能进入同一个证明。 第 00 篇定义了输入输出契约。本篇把契约连接到代码：先证明允许重复值的左边界二分，再用结构归纳证明树上聚合。输入均为有限数据，操作期间不被其他线程修改。一般性证明写在正文；有限检查由 examples/advanced-algorithms/check_foundations.py 运行。 二分查找返回的是边界 给定非降序整数数组 A，长度为 n，以及整数 x，返回最小下标 p，使得 A[p] 不小于 x。没有这样的元素时返回 n。等价地，输出要满足： 0≤p≤n,∀i<p, A[i]<x,∀i≥p, A[i]≥x.0\le p\le n,\qquad \forall i<p,\ A[i]<x,\qquad \forall i\ge p,\ A[i]\ge x. 0≤p≤n,∀i<p, A[i]<x,∀i≥p, A[i]≥x. 最后一个量词仅针对数组合法下标。数组为空...