守株阁

11 篇让更新和区间查询都保持对数成本。如果数组从建立后就不再改变，可以保存更多重叠区间的答案，换取常数次合并的查询。Sparse Table适合这种静态场景，但它的常数查询公式并不适用于所有聚合运算。 本篇先实现静态区间最小值位置查询，再用一次树遍历把最近公共祖先LCA转换成它。输入分别是不可更新的数组和合法有根树；不能把“已有预处理”当成数据修改后答案仍有效的理由。 两块为什么覆盖整个区间 数组长n，argmin(l,r)返回非空半开区间内最小值最靠左的位置，要求0≤l<r≤n。空数组可建立对象，但没有合法查询；越界或空查询抛IndexError。把每个元素表示成 (value,index)，按字典序取min，就能同时处理最小值和并列位置。 ST[k][i]保存从i开始、长2^k的完整区间答案。0层就是单元素；更高层由相邻两半合并： ST[k][i]=min⁡(ST[k−1][i],ST[k−1][i+2k−1]).ST[k][i]=\min(ST[k-1][i],ST[k-1][i+2^{k-1}]). ST[k][i]=min(ST[k−1][i],ST[k−1][...

11 篇的线段树每次改变一个叶子，再更新祖先。若给一整段元素加5，逐点更新会把许多共同祖先反复访问。可以直接修改覆盖整段的节点摘要，把尚未传播到孩子的操作保存在节点上；只有查询或更新需要进入孩子时，才继续传播。 延迟执行不是跳过执行。摘要必须立即反映当前逻辑值，标记必须足以恢复孩子未来应该看到的状态。只支持加法时，两个标记相加即可；加入赋值以后，复合顺序就成为正确性条件。 让两种更新共享一个表达式 输入整数数组，长度n，沿用11的0基半开区间。add(l,r,d)把区间每项增加d，assign(l,r,v)把每项改成v，sum(l,r)返回区间和；0≤l≤r≤n，空区间更新不产生作用，空和为0，非法区间抛IndexError。 把作用于单个元素的更新表示为仿射函数f(x)=ax+b。区间加d为(1,d)，区间赋值v为(0,v)，无操作为(1,0)。本篇a只需0或1；这种表示的目的不是引入任意线性代数接口，而是让两种操作共享可推导的复合规则。 节点摘要是(sum,len)。整段应用(a,b)后，新摘要为 (sum,len)↦(a sum+b len,len).(sum,len)\m...

数组不变时，一次前缀和预处理就能让任意区间求和变成两次读取和一次相减。若每次查询前都有一个元素变化，维护全部后缀前缀值又会变得昂贵。Fenwick树和线段树减少的是一次更新影响的摘要数量，不是让任意聚合都能通过前缀相减得到。 本篇统一接口，才能让三种结构处理同一负载。输入整数数组A，长度n；add(i,delta)令A[i]增加delta，sum(l,r)返回半开区间A[l:r]之和。合法范围为0≤i<n、0≤l≤r≤n；空区间返回0，越界抛IndexError。空数组可构造，只有sum(0,0)合法。后续区间更新、静态查询和历史版本均沿用这套边界。 前缀相减为什么成立 定义P[0]=0，P[j]为前j个元素之和。因为A[0:r]可以拆成A[0:l]与A[l:r]，所以区间和为P[r]−P[l]。线性扫描构造P耗Θ(n)，每次查询常数次算术，空间Θ(n)。点更新A[i]会影响P[i+1]直到P[n]，最坏Θ(n)。 相减使用加法逆元。若P[j]改成前j个元素的最小值，两份前缀最小值无法恢复中间区间的最小值。例如 [1,5] 与 [1,9] 的两个非空前缀最小值都为1，却有不...

不断加入无向边后，怎样判断两个顶点是否已经连通？每次重新遍历图能回答问题，但重复处理了大量已经建立的连通关系。并查集只保存连通分量划分。加入一条边时，合并两个端点所在集合即可，不必保留分量内部所有边。 这种压缩也限定了能力。并查集可以证明两个顶点属于同一集合，却不能直接返回连接路径；删去一条边后，也无法仅凭旧划分判断分量是否拆开。本篇只处理固定顶点集合上的合并与连通查询，不把它当成完全动态连通性算法。 森林表示的是什么 初始化输入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 不再变化；期望指重新抽取函数时的成...