Word-RAM 前驱问题

接口与模型 ​

抽象的 predecessor 接口也可在比较模型中研究；本页因直接使用位操作、整数宇宙和 vEB／fusion-tree 界，明确限定为Word-RAM 模型公理库Word-RAM 模型Word RAM · Word-RAM model以 w 位机器字、常数时间随机访存和明确字级操作集分析算法的随机访问机模型。。对 (S\subseteq[0,U)) 定义 (pred_S(x)=\max{y\in S:y\le x})，无解返回 (\bot)。动态版另有 insert/delete。成本须同时写 (n,U,w=\lceil\log_2U\rceil)，并假设一字容纳一键。

比较树给 $O(\log n)$；Word-RAM 可检查位和乘法，vEB 得 $O(\log \log U)$ 但朴素空间 $\mathrm{\Theta }(U)$。这些结论不适用于只能比较的任意对象，$U$ 也不能偷换成 $n$。

例子与边界 ​

(S={5,13,21}) 时 (\operatorname{pred}(18)=13)、(\operatorname{pred}(4)=\bot)。路由表可把前缀覆盖区间编码为端点事件，再用前驱恢复最长匹配。若键是超长字符串或不能装入一个字，位级结构的模型前提失效。

字典只问精确命中；前驱利用全序。范围报告还须支付输出成本。静态、动态、空间与概率保证都应分别列出。

静态排序数组以 (O(n)) 空间和 (O(\log n)) 二分提供比较基线。整数结构只有在明确宇宙、字长与可用字操作后才能突破它，并没有违反比较决策树下界。

静态与动态操作轨迹 ​

从空集插入 5、13、21 后，member$(13)$ 为真，pred$(18)=13$。删除 13 后，pred$(18)=5$，successor$(18)=21$；pred$(5)=5$ 体现本文采用非严格前驱。若业务需要严格小于，应单独定义，不能在边界键上临时改规则。

静态数组二分维护 $S[lo]\le x<S[hi]$ 的哨兵不变量，终止时返回 lo；插入却需线性搬移。平衡树把查询、插删都做成 $O(\log n)$。整数结构利用位宇宙进一步改善查询，但会引入空间、随机性或更新成本。

参数如何进入界 ​

vEB 递推 $T(U)=T(\sqrt{U})+O(1)$。连续开方 $k$ 次后宇宙变常数，即 $U^{1/2^k}=O(1)$，所以 $2^k=\mathrm{\Theta }(\log U)$、$k=\mathrm{\Theta }(\log \log U)$。朴素递归为所有簇分配空间，得到 $\mathrm{\Theta }(U)$，即使只存 $n$ 个键。

当 $U=n^{O(1)}$ 时可把时间写成 $O(\log \log n)$；没有这条关系就只能保留 $U$。Fusion tree 的 $O({\log }_{w}n)$ 又依支持哪些字操作，两式回答不同模型。

下界与相邻接口 ​

Comparison predecessor 至少要区分 $n+1$ 个间隙，决策树给 $\mathrm{\Omega }(\log n)$ 比较；Word-RAM 一次操作携带多位信息，故不受同一下界。Membership 只有命中/不命中，范围报告还要输出 $k$ 项，不能从前驱时间直接得纯查询总成本。

参考资料

• van Emde Boas et al., “An Efficient Priority Queue,” 1977.
• Dan Willard, “Log-logarithmic Worst-case Range Queries,” 1983.
• Pătraşcu, Thorup, predecessor bounds, STOC 2006.