分数级联

一次完整二分已经确定查询键在当前增强目录中的缝隙。相邻目录每隔常数个元素就把一个样本复制回来，并用桥记录对应位置，因此下一目录的正确缝隙只能在桥附近；之后只需常数次局部比较，而不必把已经获得的顺序信息丢掉再二分。

Range tree 例子 ​

二维范围树查询会访问根到分裂点附近的 $O(\log n)$ 个 $y$ 目录，且在每个目录查同一上下界。级联后只在第一个目录完整二分，随后沿预先建好的桥传播两个位置，把 $O({\log }^{2}n)$ 降为 $O(\log n)$，再加输出量。

不适用条件 ​

任意 $k$ 个毫无预处理的数组不能免费获得该界；目录关系、采样元素和桥指针占用额外空间。动态插删会让采样与桥失效，dynamic fractional cascading 需要更复杂维护。桥方向与 predecessor/successor 端点必须固定，否则等值键会产生 off-by-one。

常数定位为何成立 ​

设已知 $x$ 在 $A_i$ 的 predecessor $a$。$a$ 保存到 $A_{i+1}$ 的桥位置；因为 $A_i$ 含 $A_{i+1}$ 每隔一个采样元素，桥附近到真实 predecessor 之间至多跨常数个未采样元素。检查该位置和相邻位置即可，不需要再次二分。

若各目录长度差异大，总复杂度中的首项应写对首个增强目录规模的对数，或对总规模 $N$ 的 $O(\log N)$。查询经过的目录图路径长度为 $k$；在分支图上访问许多边时还要计实际目录数。

桥指针的局部校正 ​

第一次在 $A_1$ 二分得到位置 $p$。沿桥到 $A_2$ 后，采样保证真正 lower bound 只可能在桥位置或其相邻常数个元素中，因为 $A_2$ 每隔一个元素就被复制到 $A_1$；检查这些候选即可恢复精确位置。之后每层都重复同一局部校正，故总查询 $O(\log N+k)$，而非 $k$ 次独立二分。

桥必须分别记录增强目录位置和原目录位置。若查询需要在每个目录输出前驱，复制元素不能被误当成原目录成员；若目录之间没有固定图邻接、更新频繁破坏采样间隔，静态常数桥结论也不再成立。