守株阁

比较排序需要从比较结果中区分输入排列，因此有最坏Ω(n log n)比较次数下界。整数键还允许取位、移位和按数值寻址。利用这些操作的算法改变了模型，不能用“击败下界”来描述，也不能忽略键域和机器字长的代价。 本篇用小整数宇宙位向量实现严格前驱，再用稳定基数排序说明按位处理的成本。经典van Emde Boas结构用于解释递归缩小键域的理论方法，与16篇的静态树地址布局是不同对象。 键放进一字，不等于宇宙放进一字 设宇宙为整数集合[0,U)，当前集合有n个不同键，机器字长w位。键可以放入一字通常要求U≤2^w；若用一位表示一个宇宙元素，整个位向量放入一字却需要U≤w。两个条件相差很大。 word-RAM按字存取，指定的算术、位运算与索引按常数成本计算。若用最高置位位置直接得到前驱，还要明确提供常数时间MSB或bit-scan原语，不能只看到代码有一个函数调用就当成常数时间指令。 严格前驱定义为集合中小于x的最大键，不存在则返回空值。它不同于“小于等于x”的前驱约定。教学接口允许查询x=U以取得全体最大键；插入、删除和成员检查仍只允许0≤x<U。 一个位向量怎样实现严格前驱 令...

一维有序数组中，落在半开区间[a,b)里的键占据连续位置，两次二分就能求个数。二维点按x排序以后，一个矩形的x范围仍然连续，但其中满足y范围的点可能交错出现。把一个维度排好，没有同时解决另一个维度。 本篇先处理所有矩形查询预先给定的离线问题。扫描x时用11篇Fenwick树维护y计数，把二维条件拆成一次排序和一维动态前缀和。随后比较范围树与空间分解，说明它们为在线查询保存了哪些额外信息。 半开矩形与重复点 输入为n个整数点和q个矩形。矩形用(xlo,ylo,xhi,yhi)表示，计入满足xlo≤x<xhi且ylo≤y<yhi的点。左右或上下界倒置抛出ValueError；零宽、零高矩形返回0。重复坐标按输入中的独立点计数，空点集合法。 输出按矩形输入顺序返回计数。这里不返回点的身份列表：计数结果只有q个整数，报告查询则可能输出总计z个点引用，必须增加至少Ω(z)的写出成本。坐标比较、索引和计数加减按字长足够的RAM单位成本计算；Python大整数另有位长成本。 离线表示整个点集和查询集合在运行前已知。可以重排查询执行顺序，再用查询ID放回答案；不能据此声称同一接口支持...

17篇固定模式、扫描文本。若文本固定而查询模式不断变化，每次重新扫描长度n的文本会重复付出O(n)成本。后缀数组把文本的全部非空后缀排序，使同一模式的所有出现位置对应一个连续区间。 文本banana的后缀数组是[5,3,1,0,4,2]，依次对应a, ana, anana, banana, na, nana。查询ana得到数组中的连续两项[3,1]。结果按后缀字典序排列，不自动按文本起点递增。 固定文本的查询契约 沿用17篇Unicode码点和精确字符相等语义，不做归一化。文本长度n，查询模式长度m，命中数z。索引包含n个非空后缀；空文本的后缀数组为空。模式必须非空，否则抛出ValueError。 SuffixIndex(text).find(pattern)返回后缀数组顺序的匹配起点，保留重叠。固定文本不能原地更新：改变一个字符可能改变许多后缀的顺序，当前接口要求重新建立索引。若需要按文本位置排序，另计O(z log(z+1))时间。 后缀数组SA是起点0到n−1的一个排列，满足T[SA[r]:]按字典序递增。实现不存这些完整切片；切片只在独立的小规模参照中使用。长度为n的文本...

文本ababa中，模式aba出现在起点0和2。第一次匹配成功以后，已经读过的后缀a同时也是模式的前缀。如果把状态清零，就会漏掉第二次匹配；如果重新从每个起点比较，又重复使用了已经确定的信息。 KMP用模式的前后缀关系保存这部分信息。多个模式组成Trie以后，同一种后缀关系扩展为Aho–Corasick的失败链接。两者都让文本位置只向前移动，状态则允许回退。 输入和输出先固定 文本T长度为n，单个模式P长度为m。多模式输入是有序列表，模式数k、总长度L；重复字符串保留不同的输入ID。字符比较和数组索引先按单位成本计算，Python实现的位置是Unicode码点下标，不是UTF-8字节偏移，也不是用户可见字形编号。组合字符不自动归一化。 kmp_find(text, pattern)返回所有匹配起点，升序排列且保留重叠。空模式抛出ValueError，空文本对非空模式返回空列表。辅助函数prefix_function('')允许返回空表，这不改变匹配接口的空模式约定。 AhoCorasick(patterns).find(text)返回(起点, 模式ID)。顺序先按结束位置递增，同一...

15 篇按块容量 B 选择节点大小与归并路数。缓存无关算法不读取 B 和缓存容量 M，而用一种布局同时提供多个尺度的局部性。分析仍然依赖 B、M；“无关”限定算法可见的参数，不表示性能与硬件容量无关。 本篇只重排一棵静态完美二叉搜索树。逻辑键、左右孩子和查询序列保持相同，变化的是节点地址。这样能分辨缺失次数的变化来自布局，而不是树形或输入被换过。 理想缓存与实际替换策略 沿用15篇块传输单位，B个常数大小节点占一块，快存能保存M个节点。ideal-cache模型假设全相联：任何块可进入任何槽；替换时知道整个未来访问轨迹，选择离线最优策略OPT。算法不知道M和B，分析者知道。 LRU只根据过去访问淘汰最久未用块，是可以在线模拟的另一种策略。它不等于OPT。原论文把容量M的LRU与容量M/2的OPT比较，带有容量扩张；不能直接改写成“同样大小缓存中LRU至多差两倍”。要把这项比较转成同阶渐近界，还须满足所分析缺失函数对容量缩放的正规性，并保留缩放后所需的容量条件。 本篇模拟明确记录LRU。小轨迹另外与OPT参照比较，用于检查替换器；大轨迹的LRU数字不伪装成理想缓存定理的实测证明。这...

06 篇按键比较次数解释平衡树，09 篇用堆选择最小元素。若数据访问必须按整块搬运，相同数量的比较可能带来完全不同的块传输。一次装入多个相邻键，比沿许多互不相邻的指针访问更能利用这次传输。 本篇把 CPU 工作和块传输分开计量。块模型中的节省不自动对应某台机器的加速比；教学程序把磁盘表示成 Python 对象，统计逻辑块搬运，不进行真实磁盘性能测试。 先声明哪一层内存有界 令 N 为记录数，B 为每块容纳的记录数，M 为快存可容纳的记录数。一次块传输移动至多 B 条记录；尾块未满也计一次。快存中的比较不计为 I/O，但仍有 CPU 成本。块传输数不是系统调用数，也不是磁盘寻道次数。 归并模拟把快存容量写成 m 个块，M=mB。至少保留一个输出块；若每个输入有序段各需一个输入块，归并路数至多 m−1。堆中的段号、当前位置和最小候选还需要元数据空间：实际按字节规划内存时必须留出这部分，不能把所有可用字节都分给数据缓冲。 多路节点怎样减少点查传输 B 树把多个分隔键放在一个节点内。若一个节点放入常数个块、非根节点保持常数比例占用，分支数为 Θ(B)，高度才是 O(log_B N)。只扩...

11 篇的线段树更新一个位置时，只修改从根到叶的一条路径。如果需要保留旧数组，复制整棵树会把一次更新的空间成本扩大到线性。路径复制保留未变子树，只为这条路径分配新节点，并把新根登记为一个版本。 这里的“持久化”指旧版本仍可访问。它不表示数据已经写入磁盘，也不提供崩溃恢复、事务提交或跨进程读取能力。 版本成为接口的一部分 输入是长度 n 的整数数组，初始化产生版本 0。沿用 11 篇的点增量和半开区间和，但每个操作都指定版本： 操作 输入与输出 add(version,i,delta) 从指定版本派生新版本，只把位置 i 增加 delta；返回新版本号 sum(version,l,r) 返回该版本 [l,r) 的整数和 版本号从 0 开始连续增加，不复用。任何已有版本都能作为更新起点，因此版本之间形成分叉关系，而不是只允许不断修改最新版本。非法版本、位置或区间抛出 IndexError；空区间返回 0。空数组可以建立版本 0，但没有合法更新位置。 规模变量除 n 外还包括成功更新次数 q。所有版本根都保留在 roots 中。调用者通过公开方法操作对象，不直接...

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，却有不...