Word-RAM 前驱问题

比较模型只能逐次判断查询落在哪个有序间隙，Word-RAM 则能一次观察键的多个位并按整数宇宙分解。前驱问题因此把集合规模 $n$ 与宇宙/字长 $U,w$ 同时暴露出来；任何次对数界都在利用这份额外表示能力，而不是绕过同一个比较下界。

例子与边界 ​

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

字典只问精确命中；前驱利用全序公理库全序Total order · Linear order任意两个元素都可比较的偏序。。范围报告还须支付输出成本。静态、动态、空间与概率保证都应分别列出。

静态排序数组以 $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)$。整数结构利用位宇宙进一步改善查询，但会引入空间、随机性或更新成本。

实现的分界来自计算模型。二叉搜索树公理库二叉搜索树Binary search tree · BST每个结点左子树键小于、右子树键大于该结点键的二叉树。只用比较，在平衡时给 $O(\log n)$；van Emde Boas 树公理库van Emde Boas 树van Emde Boas tree · vEB tree按平方根宇宙递归分簇，以双对数时间支持整数前驱和动态集合操作。利用有界整数宇宙的递归分簇获得 $O(\log \log U)$，但朴素空间依赖 $U$。Fusion Tree公理库Fusion TreeFusion tree · 融合树在允许乘法和字级位运算的 Word-RAM 上，把节点内多个整数键的分叉位压成可并行比较的 sketch，从而实现次对数前驱查询。在 Word-RAM 上用字级并行一次比较多个关键位，二进制 Trie 与 Patricia 压缩公理库二进制 Trie 与 Patricia 压缩Binary trie · Patricia trie把整数视为定长位串，并以路径压缩只保留真正分叉的位置。按位前缀导航，x-fast 与 y-fast Trie公理库x-fast 与 y-fast Triex-fast trie · y-fast trie以全前缀哈希实现双对数前驱查询，再用抽样分桶把空间压到线性。再用前缀哈希和抽样平衡时间与空间。没有宇宙大小、字长和允许指令，这些界不可互换。

参数如何进入界 ​

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$ 项，不能从前驱时间直接得纯查询总成本。