x-fast 与 y-fast Trie

x-fast Trie ​

对 $w$ 位键的二进制 trie公理库二进制 Trie 与 Patricia 压缩Binary trie · Patricia trie把整数视为定长位串，并以路径压缩只保留真正分叉的位置。，在每个深度 $\ell$ 建哈希表，存所有存在的 $\ell$ 位前缀；叶按键序用双向链相连，内部节点记缺失方向对应的极值叶。查询键 $x$ 时对深度 $0,\dots ,w$ 二分，找到最长存在前缀，再由跳指针与叶链得到前驱。哈希查询期望 $O(1)$，所以前驱期望 $O(\log w)=O(\log \log U)$；空间和更新需存每个键的 $w$ 个前缀，为 $O(nw)$。

y-fast Trie ​

y-fast 只把每约 $w$ 个键选一个代表放进 x-fast trie；代表之间的桶用平衡搜索树保存。先以代表定位桶，再在桶内查前驱，查询 $O(\log w)$。随机抽样或受控分裂合并保持桶期望大小 $O(w)$，于是空间 $O(n)$，插删为期望/摊还 $O(\log w)$；保证类型来自哈希和桶重建，必须同时标明。

前缀定位例子 ​

在 8 位键集中查询 ${10110100}_2$。深度二分可能确认前缀 $1011$ 存在，而 $10110$ 不存在；该分叉节点的跳指针直接指向左侧最大叶或右侧最小叶，不必沿剩余四位逐层下降。y-fast 再把这个候选代表映到只含 $O(w)$ 个实际键的桶。

易混边界 ​

x-fast 的查询快但空间不是线性；y-fast 的线性空间依赖抽样代表和桶维护，不能把两者的最好指标拼成一个无条件表。$O(\log w)$ 是 $O(\log \log U)$，不是 $O(\log \log n)$。哈希表的期望、对手是否适应随机种子、桶过大时重建成本都属于结论前提。

更新维护 ​

x-fast 插入一个键要把其至多 $w+1$ 个前缀加入对应哈希表，并修复首次分叉路径上的 descendant pointer 与叶链，因此更新期望 $O(w)$，不是查询的 $O(\log w)$。删除还要移除不再被其他键共享的前缀。

y-fast 将这份昂贵更新只用于桶代表。桶超过常数倍 $w$ 时按中位数分裂并插入新代表，过小时与邻桶合并；一次重建 $O(w\log w)$ 可向此前 $\mathrm{\Omega }(w)$ 次更新摊还。随机抽代表的原始版本与确定阈值分桶版本保证常数不同，不能混写成“最坏 $O(\log w)$”。

一次 y-fast 更新拆成什么 ​

插入键 $x$ 时先用 x-fast 代表集合找到所属桶，再在桶内平衡树插入。若桶大小超过阈值，例如 $2w$，就在中位键处分裂成两个大小约 $w$ 的桶：删除旧代表、为两桶选择新代表，并更新代表的所有前缀表。删除后桶过小则与邻桶合并或重分配。

一次代表变化要改 $O(w)$ 个哈希项，看似昂贵；但只有累计 $\mathrm{\Theta }(w)$ 次桶内更新才触发分裂或合并，故这部分摊还到每次更新为期望 $O(1)$，桶树操作仍为 $O(\log w)$。完整保证为：哈希模型下查询、插入、删除均为期望 $O(\log w)$，空间 $O(n)$；它不是确定性最坏 $O(\log \log U)$。

代表键必须真正在桶边界上，并同步维护叶链。只更新哈希前缀、不更新代表顺序链，会让最长前缀命中正确却跳到错误相邻桶，这类错误通常只在查询落入两个代表之间时出现。

x-fast 的 $O(nw)$ 空间来自每个键贡献从根到叶的 $w+1$ 个前缀；y-fast 只为每个大小 $\mathrm{\Theta }(w)$ 的桶保留一个代表，所以代表数 $O(n/w)$，前缀总数降为 $O(n)$。这一步空间抵消是 y-fast 的核心，不是把桶换成平衡树后自动发生。

当 $n<w$ 或桶数量很少时，可直接用一棵桶内树处理，避免建立空洞的代表层。宇宙端点、空集合以及查询小于最小键或大于最大键时，都应通过叶链哨兵返回“不存在”，而非溢出到补齐宇宙的虚拟键。

参考资料

• Dan Willard, Log-Logarithmic Worst-Case Range Queries are Possible in Space Θ(N), Information Processing Letters, 1983.
• Gonzalo Navarro, Compact Data Structures, predecessor search chapters, 2016.