守株阁

第14篇用版本根保留旧状态。对旧版本发起查询，得到的答案不会因为新版本产生而改变。追溯数据结构允许编辑过去的操作序列，之后的历史查询则按照编辑后的序列重新解释。两个接口都出现时间参数，但承诺保留的东西不同。 本篇只实现整数增量事件：在指定时间插入一个加法，或删掉已有事件，再查询某时刻之前的累计和。这个有界操作集可以用排序数组与前缀和实现，足以验证语义，不需要先实现一个通用追溯框架。 两种时间不能混用 把一次编辑请求的提交次序记为版本编号v，把事件在被建模历史中的位置记为时间t。提交顺序可以是先录入t=10，再录入t=2。版本编号仍向前增长，逻辑时间却不要求按输入顺序排列。 持久化保留v所指的旧状态；完全持久化允许从旧版本分支产生新版本，原分支仍存在。追溯编辑把t=2处的事件放入当前解释的历史，此后查询t=3就必须计入这个事件。若还要求查看“编辑之前看到的历史”，需要额外保存编辑版本，本实现没有这个接口。 需求 被查询的对象 新编辑对旧查询的影响 持久化查询版本v 固定版本状态 相同v的答案不变 追溯查询逻辑时间t 当前事件序列在t前的状态 编辑早于t的事件可能改...

把0和1放进整数数组，可以做前缀计数，但“数组长度是n”不等于“占n位空间”。简洁数据结构要求先确定信息下界，再计算索引冗余；指针、绝对计数和查找表都不能从空间账本中消失。 本篇实现静态位向量的rank/select接口，用Python参照和C++固定字长实现核对查询。教学实现采用简单分块索引，明确不把它称为已经实现n+o(n)位的succinct结构。 一种查询数个数，另一种查询找位置 输入为长度n的二进制序列B，元素只能为整数0或1，构造后不再修改。rank1(i)返回半开前缀B[0:i]中1的数量，0≤i≤n；select1(k)返回第k个1的零基位置，k从1开始，沿用00与06篇的顺序统计约定。 空序列可以构造，rank1(0)=0，但任何select都越界。全零序列也没有合法select。非法位值拒绝，rank端点或select序号越界拒绝，不用某个特殊位置冒充答案。 例如B=[0,1,0,1,1]，rank1(3)=1，select1(2)=3。这里rank参数是位置端点，select参数是出现序号；若p=select1(k)，则rank1(p)=k−1、rank1(...

地面没有条纹纹理，渲染结果却出现整齐的明暗带。增大一个深度偏移参数后，条纹消失；继续增大，立方体明明贴着地面，阴影却与底边分开。前一种是错误自阴影，后一种是偏移过大造成的漏影。 本篇固定几何、相机、光源和分辨率，只改变偏移。除了三张实际图像，还用独立射线与盒相交判断地面是否真的被遮挡，分别统计“错误变暗”和“错误受光”，不把看起来干净的图直接认定为正确。 从光源再做一次可见性判断 第06篇从相机出发，为每个像素保存最近表面的深度。阴影映射把同一思路用于光源：第一遍从光源观察场景，保存最近表面的光源深度；第二遍从相机观察可见表面，将每个表面位置投回光源空间，与第一遍比较。 一个表面可能被相机看见，却被另一块几何挡住光源。因此相机深度测试和阴影比较各自回答不同问题，不能复用相机深度值直接判阴影。 设接收点在光源NDC中的深度为z，阴影图在对应位置保存D。沿用近处0、远处1的约定，若z>D，接收点比光源看见的最近表面更远，应被遮挡。加入接收点偏移b后，当前判断为： shadow=[z−b>D].\text{shadow}=[z-b>D]. shadow=[z−b&g...

第10篇并查集只保存连通分量划分。加入边可以合并集合，删除边却不能直接拆开集合：被删边可能是唯一通路，也可能还有其他路径。若全部操作预先已知，可以改变处理顺序，让每段递归只做合并，在离开时撤销这些合并。 本篇实现回滚并查集与时间线段树，回答一般无向图的离线加边、删边与连通查询。它不依赖第13篇运行程序，也不提供在线到达即回答的接口。 图边与代表元指针不是同一回事 输入有n个固定顶点，编号0到n−1，以及q个操作。每个操作为add(u,v)、remove(u,v)或query(u,v)，结果按query出现顺序返回布尔列表。所有端点先检查，越界抛IndexError；n为负、未知操作、重复添加已存在的边或删除不存在的边抛ValueError。 无向边统一为(min(u,v),max(u,v))，同一对端点同时最多存在一条边。允许自环，但自环不会改变连通性；删除后可以重新添加，形成新的生命区间。这里没有平行边引用计数，不能把重复add当作第二条独立边。 并查集的parent指针是分区表示，不要求它对应输入图中的某条边。删除图边(u,v)不能解释成“把parent[v]设回v”。例如三...

把模型横向拉长两倍，轮廓变化正确，高光却可能出现在错误位置。顶点位置和法线若都乘同一个缩放矩阵，程序不会报错，但法线已经不再垂直于表面。 本篇先用点积定位这个问题，再用同一个32三角形曲面比较平面与平滑着色。几何、覆盖与光源不变，只改变着色法线；所有颜色仍在线性域计算，最后沿用第04篇的sRGB输出。 法线保存的是垂直关系 三角形顶点为p0,p1,p2p_0,p_1,p_2p0​,p1​,p2​时，两条边e1=p1−p0e_1=p_1-p_0e1​=p1​−p0​、e2=p2−p0e_2=p_2-p_0e2​=p2​−p0​位于表面内。非退化三角形的单位几何法线为： ng=e1×e2∥e1×e2∥.n_g=\frac{e_1\times e_2}{\|e_1\times e_2\|}. ng​=∥e1​×e2​∥e1​×e2​​. 交换顶点绕序会改变叉积符号。零面积三角形没有唯一的面方向，本系列仍拒绝对零向量归一化，不通过更换分母掩盖退化几何。 顶点上还可以存一组用于着色的法线。它们可以来自原始光滑曲面，也可以由相邻面按明确权重平均。几何法线描述三角形本身，着色法线描述希望使用...

“每个位为1的概率算对了，把它乘k次就得到精确误报率”是一个可以检验的判断。第33篇已经给出小反例，本篇把它整理成一个完整复现项目：明确概率空间，用两个独立方法计算有限实例，保存原始结果，再说明哪个判断被否定、哪个一般结论需要证明。 研究对象是理想Bloom模型的公式，不是本系列仿射散列教学实现的实际误报率。38篇区分精确结果与测量精度，这里更进一步：全程使用有理数，不让浮点舍入成为公式差异的解释。 先写出概率空间 位数组有m个位置，m≥1，初始全为0。插入n个不同键，n≥0，每个键使用k个哈希位置，k≥1。所有kn个位置独立、均匀地取自0到m−1，允许一个键的多个位置相同。 随后查询一个固定的未插入键，它的k个位置也独立均匀，并独立于插入阶段。若查询的所有位置都已置1，就发生误报。n计不同键；重复插入同一个键会重用哈希值，不能按新的一组独立投球计算。 这个模型不自动覆盖双重散列、同一键无放回选择k个位置，或看过位数组再挑查询的对手。代码不会调用33篇的仿射Bloom来伪装这个完全独立模型；二者的随机假设不同。 精确式在条件概率之后取平均 令X为插入结束后的置位数。给定完整位数组...

斜边变得平滑以后，地板上的细棋盘仍可能随着相机移动而闪烁。这两种现象都涉及采样，但需要平均的对象不同：轮廓处要估计像素有多少面积被图元覆盖；图元内部则要估计一个像素对应的纹理区域里有哪些颜色。 第07篇已经修正透视UV插值。本篇继续区分“采样位置正确”与“采样区域充分”，用两个互相独立的CPU实验验证覆盖采样和纹理预滤波。它们采用明确的规则网格，不代表某块GPU的实际多采样布局。 一个像素需要的是区域信息 先选盒式像素滤波器，把像素看成单位正方形。对黑色背景上的白色图元，理想线性颜色等于图元与像素相交的面积，范围为[0,1]。若恰好覆盖四分之一，颜色应为0.25，再经过sRGB编码用于显示。 在像素中心只问一次“是否在三角形内”，只能得到0或1。沿斜边移动时，这个判断会突然翻转。增加覆盖样本可以得到更多中间值，但有限点集仍是面积的近似，不等于精确积分。 本实验的64×64视口中，白色区域在直线y=0.375x+8.25y=0.375x+8.25y=0.375x+8.25上方，屏幕Y仍向下。它由两个三角形组成，四角为(0,0)、(64,0)、(64,32.25)、(0,8.25)...

第36篇的两个榜单实现回答相同查询，却把成本放在不同位置。VersionedBoard维护AVL和路径复制树，SnapshotBoard复制完整字典并扫描或排序。对数复杂度并不能直接回答“小数据上哪个Python实现更快”，一次本机测量也不能回答“所有负载都该选哪个”。 实验先固定语义，再改变输入规模、分数分布、更新比例与整数位长。近似算法允许不同输出质量，应另外报告质量，不能让它与精确实现只比一个耗时数字。 同一语义的比较需要固定什么 榜单实验沿用36篇契约：ID稳定、排名按(-score,id)、范围按ID半开区间、历史查询指向明确版本。两种实现从相同初始分数开始，执行完全相同的更新与查询，保留全部历史版本。 输入规模n取16、64、256；分布包含重复分数多的tied与较分散的uniform；更新比例取0.1、0.8。每条操作流长度256，查询按rank、select、当前随机范围和、历史全域和轮换。历史全域查询在持久化树上可直接读取根摘要，不代表任意历史子区间都只访问根。更新率是生成概率，实际更新数另记。输入在计时外生成并保存散列，结果校验和相等是进入比较的条件，不是“答...

“安排合适的人完成任务”和“用最低成本覆盖全部目标”都包含选择，但它们选择的对象、限制和目标不同。二分图匹配的最优证书，不能替一个集合覆盖方案证明成本最优；覆盖了所有目标，也不代表有足够人员执行选中的方案。 本篇复用27篇的二分图匹配和30篇的加权集合覆盖贪心。两种输出分别验收，只有明确增加联合模型后，才能讨论联合方案的可行性与最优性。 资格分配：每个人和任务最多出现一次 输入是a名人员、b个任务，以及m条资格边。边(u,v)表示人员u可以执行任务v，左右编号属于两个独立集合。每个人至多承担一个任务，每个任务至多由一人承担；所有任务价值相同，目标是最大化被分配任务数。 输出包括匹配边的原始编号，以及由左侧人员和右侧任务组成的点覆盖。点覆盖必须接触每条资格边，不能把集合覆盖中的“覆盖所有目标”直接套到这里：这里覆盖的是图的边。 验证先检查匹配边都在输入中，左右端点没有重复，再检查点覆盖接触所有资格边。如果匹配大小等于点覆盖大小，就得到最优证书。理由是任何匹配的边两两不共享端点，而点覆盖必须为每条匹配边提供至少一个端点，所以任意匹配大小都不超过任意点覆盖大小。 当两者相等时，下界与上...

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