van Emde Boas Tree 速通版

Seauy · 2022-06-02 00:27:50 · 个人记录

以下内容源自《算法导论》。

零. 标记与约定

定义记号，若 n=2^k\ (k\in Z^{+})，则

\sqrt[\uparrow]{n}=2^{\lceil \frac{k}{2} \rceil},\ \sqrt[\downarrow]{n}=2^{\lfloor \frac{k}{2} \rfloor }

high(x)=\lfloor \frac{x}{\sqrt[\downarrow]{n}} \rfloor,\ low(x)=x\bmod \sqrt[\downarrow]{n}

index(a,b)=a\sqrt[\downarrow]{n}+b

空与值的比较为未定义运算，出现未定义运算的命题为假命题、表达式的结果为空。
对于变量类型结合语境灵活变通，如 A 既可以为值又可以为一棵 vEBT，因为在固定根的语境下一个值能表示一个儿子。
在没有强调根的指定的情况为默认用 r 表示。

一. 理论性能

可以维护 [0,n) 的整数集合（当 n 不为 2 的幂时取 2^{\lceil \log_2 n \rceil}），在线非均摊，支持的操作：

建树，时空 O(n)。
查询集合内最小/最大值，时间 O(1)。
查询值是否在集合内，时间 O(\log \log n)（有数组辅助可以做到 O(1)）。
查找前驱后继，时间 O(\log \log n)。
插入元素，时间 O(\log \log n)。
删除元素，时间 O(\log \log n)。

二. 原理

本质是个多叉线段树，复杂度得以突破的点在于：

对于一个结点的所有儿子，vEBT 递归构建了与其儿子规模一致的 summary 儿子维护多叉的信息。
维护了区间内最值，并且最小值并不真的存在子结构中，而是作为根节点的标记。

(一). 建树

要保证集合初始为空。

对于一个维护 [0,n) 的 vEBT，其儿子为 \sqrt[\uparrow]{n} 个维护 [0,\sqrt[\downarrow]{n}) 的 vEBT，第 i 个儿子（i\in [0,\sqrt[\uparrow]{n})）维护的区间对应 [0,n) 的子区间 [i\sqrt[\downarrow]{n},(i+1)\sqrt[\downarrow]{n})；以及维护各个儿子信息的维护 [0,\sqrt[\uparrow]{n}) 的 summary 儿子，若第 i 个儿子中有元素，summary 就包含元素 i。

递归建树即可，当 n=2 的时候成为叶子结点。

时空复杂度相等，皆为：

T(n)=(\sqrt{n}+1)T(\sqrt{n})+O(\sqrt{n})=O(n)

当 vEBT 中没有元素时，min/max 皆指向空。

(二). 最值查询

因为根节点储存了整个集合内的最值，直接返回即可。

定义 GetMax(r) 为 vEBT r 中的最大值，若维护的是空集则返回空，GetMin(r) 类似。

(三). 存在查询

如果可以开 O(n) 大小的 bool 数组辅助，那么此操作就是 O(1) 的。

否则，设查询的值为 x，此时到达的结点维护 [0,n)，则进入第 high(x) 个儿子，查询其是否有元素 low(x)，直到到达叶节点，通过 min/max 标记判断。

时间复杂度 T(n)=T(\sqrt{n})+O(1)=O(\log \log n)。

(四). 前驱后继查询

由于最值信息记录不对称，前驱后继查询分开讨论。

前驱后继查询函数定义为 Pred(r,x),\ Succ(r,x)，表示在 vEBT r 进行对于值 x 的查询，若不存在前驱后继返回空。

后继查询

若为叶子结点，当且仅当 x=0 且最大值为 1 的情况下有后继，否则返回空。

若为非叶结点，首先我们得知道 x 的后继在哪个子树。

如果在第 high(x) 个儿子中，满足 GetMax(high(x))>low(x)，返回 index(high(x),Succ(high(x),low(x)))。

其他情况，进入 summary 寻找 high(x) 的后继 s=Succ(summary,high(x))，返回 index(s,GetMin(s))。

前驱查询

叶节点情况类似。

非叶结点，若 GetMin(high(x))<low(x)，说明前驱与 x 在同一个子树内，返回 index(high(x),Pred(high(x),low(x)))。

其他情况，寻找 high(x) 前驱 p=Pred(summary,high(x))。

此时需注意，p 为空不代表不存在前驱，这是因为前驱可能为这棵 vEBT 的最小值，但最小值不会存储在子树中，因此在 p 为空的情况下，若 GetMin(r)<x 返回 GetMin(r)，否则返回空。

在 p 不为空的情况下，返回 index(p,GetMax(p))。

发现在这两种查询中，子树的 Pred/Succ 最多被递归一次，因此时间复杂度

T(n)=T(\sqrt{n})+O(1)=O(\log \log n)

(五). 插入操作

假设插入元素不在 vEBT 中。

由于我们不真的存入最小值，对于一个空地 vEBT 插入居然是 O(1) 的！

若当前 vEBT 为空，直接把 min/max 都改成 x。

其他情况，交换 x 与 GetMin(r)，从插入 x 变化成插入 GetMin(r)，先更新 GetMax(r)。

如果不是非叶节点，我们要把 x 插入儿子 high(x) 中并对 summary 做对应修改。在 high(x) 为空的情况下，O(1) 插入儿子并递归修改 summary；其他情况，只用向 high(x) 递归即可。

发现每次最多只递归一次，时间复杂度依旧是 O(\log \log n)。

(六). 删除操作

假设删除元素不在 vEBT 中。

若 GetMin(r)=GetMax(r)，说明只有一个元素，将 min/max 改为空即可。

现在集合内至少有两个元素。若 n=2，说明在叶结点，随便讨论一下即可。

其他情况，若删除的是最小值，O(1) 找出 r 的次小值并赋值给 x，把 min 改成 x。

无论是 min 变过来的 x 还是一直以来的 x，都不应该存在于子结构中，因此进入对应儿子递归删除。

接下来若 high(x) 维护空集合，还需要在 summary 中删除 high(x)，然后维护 r 的最大值，在 summary 中找最大值对应到 [0,n) 中，删除后只剩一个元素的情况单独讨论。

若 high(x) 不为空且删除最大值，直接在 high(x) 中找最大值即可。

虽然最多的时候会递归两次，但第二次 summary 的修改当且仅当 high(x) 被删空，此时 high(x) 的递归是 O(1)，因此时间复杂度为 O(\log \log n)。

三. 代码（施工中）

咕咕咕

四. 实际性能（施工中）

打算搞个模板题。

五. 拓展（施工中）

支持重复关键字

开个数组记录副本数即可。

大值域 vEBT

直接动态开点时间是对的，空间是错的（如果认为申请空间不算在时间复杂度之内的话），具体看操作次数与值域的相对规模，注意此时无法使用辅助数组。

RS-vEBT 使用哈希表存储指针，只有非空结点才占用空间，可以证明空间 O(q)（与操作次数同阶），因为当新元素进入空结点就停止递归，一次操作增加的空间复杂度是 O(1)。但是常数应该会很大，实现复杂，在OI界没有太大实用价值。

Patrascu 和 Thorup 证明了在允许引入随机化的情况下，vEBT 的 O(\log \log n) 是前驱后继查询的下界。