van Emde Boas 树

宇宙递归 ​

令键宇宙为 $[0,U)$，先补齐到 $U=2^{2^k}$。把键写成高、低两半：

$$\mathrm{high}(x)=\lfloor x/\sqrt{U}\rfloor ,\mathrm{low}(x)=xmod\sqrt{U},\mathrm{index}(a,b)=a\sqrt{U}+b.$$

结构保存 min/max，为每个非空高位建立大小 $\sqrt{U}$ 的 cluster，并用一个同规模 summary 记录哪些 cluster 非空。

操作与递归式 ​

前驱查询先在 $x$ 所属 cluster 寻找低位前驱；若不存在，就在 summary 找更小的非空 cluster，再取该 cluster 的 max。插入第一个元素只更新 min/max；某 cluster 从空变非空时还要插入 summary。删除 min 时必须从 summary 找首个非空 cluster 提升新 min，并在 cluster 变空时同步删除 summary 项。

每层只递归进一个规模 $\sqrt{U}$ 的子结构：

$$T(U)=T(\sqrt{U})+O(1)=O(\log \log U).$$

十六元宇宙例子 ​

$U=16$ 时高低各两位，共四个 cluster。集合 $\{2,3,12\}$ 在 cluster 0 存低位 $\{2,3\}$，cluster 3 存 $\{0\}$，summary 为 $\{0,3\}$。查询 10 的前驱时 cluster 2 为空，summary 的前驱是 0，于是返回 cluster 0 的 max，即 3。

空间与模型边界 ​

朴素递归为所有 cluster 预留结构，空间满足 $S(U)=(\sqrt{U}+1)S(\sqrt{U})+O(1)=\mathrm{\Theta }(U)$。当 $U\gg n$ 时不可接受，x/y-fast Trie公理库x-fast 与 y-fast Triex-fast trie · y-fast trie以全前缀哈希实现双对数前驱查询，再用抽样分桶把空间压到线性。以哈希和抽样换线性空间。时间依赖宇宙 $U$ 而非元素数 $n$；它需要整数可分位操作，不适用于任意比较键。

Base case 与 min 特判 ​

$U=2$ 时可直接以两个 bit 维护成员。一般节点把全局 min 单独放在 cluster 外：插入小于当前 min 的键时先交换，让旧 min 递归进入 cluster；这使空结构和首元素插入为常数。前驱查询若 $x>\min$ 且所属 cluster 无更小低位，才去 summary 找前一 cluster；若 summary 也无前驱，最后仍可能返回全局 min。

删除最大值同样需在最后非空 cluster 消失时从 summary 与 cluster max 重算。min/max 特判减少递归，却是实现最容易遗漏的正确性分支。

空簇查询的返回路径 ​

求 successor(x) 时，先看 $x$ 所在簇中是否有大于 low(x) 的元素；若有，就在该簇递归。若没有，转而在 summary 中求下一个非空簇编号 $j$，答案是 index(j, cluster[j].min)。summary 也无后继时返回不存在。这个分支解释了为什么每簇必须显式维护 min，也解释了空簇不能先递归再访问其字段。

当 $U=2$ 时直接用两个比特或 min/max 回答，递归停止。若实际键宇宙不是二次幂，可向上取整并拒绝填充区间中的假键；若只说“压缩坐标”，动态插入新键会改变秩，已不再是原本的在线前驱问题。

参考资料

• Peter van Emde Boas, Robert Kaas, Erik Zijlstra, Design and Implementation of an Efficient Priority Queue, Mathematical Systems Theory, 1977.
• Cormen et al., Introduction to Algorithms, van Emde Boas Trees.