分数级联

目录与增强 ​

给一条目录链 $C_1,\dots ,C_k$，每个目录按同一全序公理库全序Total order · Linear order任意两个元素都可比较的偏序。排列。自后向前构造增强目录

$$A_i=C_i\cup \text{every-second}(A_{i+1}),$$

并为增强元素保存到原目录 $C_i$ 与下一增强目录 $A_{i+1}$ 的邻近位置桥。固定采样比例使总增强规模为原目录总规模的常数倍。

查询不变量 ​

先在 $A_1$ 对键 $x$ 做一次 $O(\log N)$ 二分。已知 $x$ 在 $A_i$ 的相邻元素后，通过桥落到 $A_{i+1}$，因每隔一个元素被采样，只需检查常数个邻居即可恢复正确 predecessor。沿 $k$ 个目录总查询

$$O(\log N+k).$$

有界度目录图可推广相同思想；高出度会复制过多桥。

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$ 次独立二分。

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

参考资料

• Bernard Chazelle, Leonidas Guibas, Fractional Cascading I: A Data Structuring Technique, Algorithmica, 1986.
• Kurt Mehlhorn, Stefan Näher, Dynamic Fractional Cascading, Algorithmica, 1990.