分数级联

一次完整二分确定了查询键在当前目录中的缝隙。下一目录每隔一个记录就有一个样本复制回来，因此这个缝隙里不可能隐藏很长的未知段。桥把位置带过去，只需一次局部修正；之后不用重新二分。

复制样本帮助导航，却不是本层原始数据。回答“第几条原记录”或做范围报告时，必须回到原目录指针，不能把桥记录当作额外对象输出。

一次需要局部修正的查找 ​

取 $C_2=(1,4,7,10,13)$，样本为 $(4,10)$，再取 $C_1=(3,8)$，于是 $A_1=(3,4,8,10)$。查询 $x=2$ 时，首层没有前驱，从哨兵的桥落到 $A_2$ 的位置 $-1$。下一记录为 $1\le 2$，前进一步后，$4>2$，所以第二层前驱为 $1$；第一层仍返回不存在。

查询 $x=9$ 时，首层前驱为 $8$，桥指到第二层的 $7$；下一项 $10>9$，无需前进。两层的原目录答案分别为 $8$ 和 $7$。

重复值也要按位置保存。若 $C_2=(4_a,4_b,4_c,8)$，第一个采样记录是 $4_b$；查询键 $4$ 时，桥须指向等值段末尾 $4_c$，不能因为样本来自 $4_b$ 就把它误报为最后一项。记录身份与键值相等是两件事。

为什么至多修正一步 ​

设 $a$ 是 $x$ 在 $A_i$ 中的最后一个前驱。桥已经定位到 $A_{i+1}$ 中键不大于 $\mathrm{key}(a)$ 的最后一项。从那里到真正答案之间，所有新遇到的键都在 $(\mathrm{key}(a),x]$。若至少有两个这样的记录，连续位置中必有一个被每隔一项的采样选中，并复制进 $A_i$；它会成为比 $a$ 更靠后的合法前驱，矛盾。因此最多只有一个未采样记录需要跨过。哨兵情况是同一个首段论证。

同理，$C_i$ 不会另有键落在 $(\mathrm{key}(a),x]$，因为其全部记录本就包含在 $A_i$。所以 $a$ 保存的本层原目录位置也是 $x$ 的正确答案。空目录、查询小于全部键或大于全部键都由这些边界位置统一处理。

二维范围树理路范围树range tree以主坐标搜索树和节点关联目录支持固定维正交范围查询。查询沿树访问相关的 $y$ 目录。共享两个纵向边界位置，可把原先每张表独立二分的 $O({\log }^{2}n)$ 定位工作降为 $O(\log n)$，报告仍另加 $k$ 项输出。这里闭区间下端需要 lower bound、上端需要 upper bound；可对严格前驱与非严格前驱分别建立一致的桥约定，不能把本页的最后一个 $\le x$ 位置直接当成第一个 $\ge x$。

目录链是最清楚的基型。原始分数级联定理还允许有界度目录图，并按实际经过的边传播搜索；采样密度和桥结构要适应该度界，不能把链上的“每隔一项复制”不加修改地套给任意分支图。任意不相邻的目录也不能免费获得桥定位。

动态插删会改变采样位置与桥，需另行维护动态分数级联结构。静态定理不会自动给出相同更新界。首项对数取决于首个增强目录大小，可用 $O(\log (N+1))$ 统一上界；其后工作则取决于实际访问的目录数。