土法炼钢 · 系统与基础设施

van Emde Boas 树：整数前驱查询的递归结构、空间代价与下界

2026-04-23 | algorithms | #veb-tree #predecessor-search #word-ram #y-fast-trie #hierarchical-bitmap #cell-probe-lower-bound #linux-scheduler

vEB 树把 w 位整数键逐层对半拆分，使前驱查询每层只递归一次，代价是与宇宙大小成正比的空间。本文给出经穷举测试的 C 实现，用调用次数、字节数和绑核计时对比 std::set 与 64 叉分层位图，并梳理从 1975 年原论文到 Pătraşcu–Thorup 下界的谱系。