vEB-Tree 学习笔记

· · 算法·理论

背景

一切的一切都来自于一道题的 SPJ，要求写一个判断选手输出的数字在不在给定的集合里面的 SPJ，我一开始看这个觉得问题并不是很大，直到一看输出数量 1\le n\le 2\times 10^7，值域 0\le a_i\le 10^9。

啊呀，骇死我力！

后面发帖求助了一下谷民的智慧，然后就引出来了这个神奇的数据结构。（虽然说 vEB 树并不能解决这道题）

问题的引入

首先引入 V 表示值域。

考虑这样一系列问题：

  1. 给你一个集合，多次询问，每次询问一个数字是否存在于这个集合之中：

在值域小的情况下，开桶即可解决该问题。

  1. 在上述基础上，支持插入与删除操作：
3. 在上述基础上，支持查找最大最小值： 在 $O(V)$ 预处理时统计最大最小值，修改时只需在修改的同时修改最大最小值即可。 4. 在上述基础上，支持查询一个数的前驱后继： 此时，你的桶数组就会在极限数据下超时到飞起来。 那么有人就会说了：**我用平衡树不就好了！这有什么难度？** 是的，以上几种操作都可以简单地用平衡树进行实现，并且单次操作复杂度到达了优秀的均摊 $O(\log n)$。 但是我们今天所介绍的主角：vEB 树，能在 $O(\log\log n)$ 的时间复杂度内完成单次操作。你可能有点不了解，$O(\log\log n)$ 到底比 $O(\log n)$ 快多少，以下是一张简单的函数图像，用于对比： ![](https://cdn.luogu.com.cn/upload/image_hosting/o2ifw13r.png) $y$ 表示计算量，$x$ 表示数据规模。（下文中 $n$ 与 $x$ 意义相同） 当 $y=10^8$ 时（笔者认为通常情况下计算机在 $1$ 秒钟内的计算量约为 $10^8$），$O(n\log n)$ 可承受的数据规模约为 $5\times 10^6$，而 $O(n\log \log n)$ 可承受的数据规模约为 $2\times 10^7$！我们考虑适当的程序常数，那么 $O(n\log n)$ 可承受的数据规模约为 $10^6$，而 $O(n\log \log n)$ 可承受的数据规模约为 $5\times 10^6$。这个运行速度相当的惊人了，要知道很多题目对于 $O(n)$ 的算法一般都开到 $10^7$ 为止。那么我们可以**近似**把 vEB 树的各种操作看成 $O(1)$ 了！ 那么这么优秀的数据结构，为什么会变得如此冷门呢？以下是它的缺点： 1. 各种操作的关键字必须是 $[0,n-1]$ 的整数。 2. **建树时的预处理复杂度为** $O(V)$！ 也就是说 vEB 树是基于值域的，这大大地限制了其使用的空间，但即使这样，vEB 树也被称为最有用的数据结构之一。 另注：在 vEB 树中，关键字要求不重复，但是在处理时可以先查询该元素的存在性，若关键字重复，在对答案无影响的情况下跳过该次处理即可。 # 一切算法的出发点 一切算法的出发点不就是为了更高效地解决一个问题吗。（确信） 让我们回到上文提到的问题，对于一个集合 $S$，需要支持以下操作： 1. 判断数 $x$ 是否存在于 $S$ 中。 2. 插入数 $x$ 到 $S$ 中，从 $S$ 中删除数 $x$。（不保证插入时 $S$ 中没有 $x$，保证删除时 $S$ 中有 $x$） 3. 查询 $S$ 的最大最小值。 4. 询问一个数在 $S$ 中的前驱后继。 操作数 $m$ 与元素个数 $n$ 都不超过 $10^5$。 我们先保证 $S$ 中任意数都在 $[0,10^7)$ 中，并把平衡树与权值线段树抛开，如何做这道题？ ## 优雅的暴力 既然 $n,m$ 都不超过 $10^5$，那么我们可以想到一个 $m\times \sqrt{n}$ 的做法：块状数组。 我们可以建立如下图的块状数组： ![](https://cdn.luogu.com.cn/upload/image_hosting/i47g4ikx.png) 其中，原数组表示该数在集合中的存在性，而块则表示该块所代表的区间中的任意一个数的存在性。也就是说一个块的值为该块内所有数组元素的逻辑或。本文所有的图中用红色表示 `0`，绿色表示 `1`。 接下来就是对于各种操作了： 1. 直接访问原数组，时间复杂度 $O(1)$。 2. 进入原数组并修改对应值，修改完成后更新块的状态，最劣复杂度 $O(\sqrt{n})$。 3. 遍历块，找到第一个（查找最大则倒序遍历）值为 `1` 的块，进入并遍历该块找到第一个值为 `1` 的元素。最劣复杂度 $O(\sqrt{n})$。 4. 先找到该元素，随后遍历该元素所在块，若块中该元素是最小的，则向前遍历块直至找到值为 `1` 的块，进入并找到最大的值为 `1` 的元素即为前驱（后继类比即可）。最劣复杂度 $O(\sqrt{n})$。 这样我们便解决了该问题。 ## 分治的妙招 接下来，我们把 $n,m$ 扩大到 $10^6$ 级别，又该如何应对呢？ 显然我们需要 $O(\log n)$ 的单次操作复杂度。 还是从优化原数组的思路出发，我们可以在该数组上建立一颗二叉树： ![](https://cdn.luogu.com.cn/upload/image_hosting/nk3htzhf.png) 那么每一个节点的值即为其两个儿子的逻辑或。 好吧这确实很像线段树，处理方式也很像。 1. 访问原数组即可，时间复杂度 $O(1)$。 2. 修改原数组，随后向上递归并计算新逻辑或，时间复杂度 $O(\log n)$。 3. 对于查询最大值，我们从根节点出发，一直向下递归，并优先走值为 `1` 的**右儿子**，若右儿子值为 `0` 再走左儿子。最小值类比即可。时间复杂度 $O(\log n)$。 4. 对于查询一个数的前驱，我们从原数组出发，一直向上递归，若我们是从左儿子进入其父亲节点的，那么继续向上递归，若我们是从右儿子进入其父亲节点的，那么以其父亲节点的左儿子为根，查询最大值即可。后继可以类比得到。最劣时间复杂度 $O(\log n)$。 以下的图是查询 $9$ 的前驱的例子： ![](https://cdn.luogu.com.cn/upload/image_hosting/q8yknfj3.png) 这样我们便将时间复杂度由 $O(m\times \sqrt{n})$ 优化为了 $O(m\log n)$。 # 更高效地处理 那么如果我们继续提升规模，使 $n,m$ 达到 $10^7$ 的规模呢？（从此开始，本文视 $V,n,m$ 同阶。） 这时候就要请出我们的主角：vEB 树了。 vEB 树全名为 van Emde Boas 树，是由一位名为 $\texttt{Peter van Emde Boas}$ 的荷兰计算机科学家发明的，故名 vEB 树。 首先我们回到块状数组上面去，我们给这个“块”改一个名字，称为“簇”。而 vEB 树就与这个“簇”有着密切的联系。 ## 原型 vEB 树 本节中，我们钦定 $V=\{2^{2^k}:k\in \mathbb{N}\}$，在这样的前提下，容易证明 $V$ 可以一直开 $k$ 次平方根并始终为整数。 ### 一些定义 1. $\operatorname{high}(x)=\lfloor \frac{x}{\sqrt{V}}\rfloor
  1. \operatorname{low}(x)=x \bmod \sqrt{V}
  2. \operatorname{index}(x,y)=x\times \sqrt{V}+y

那么这些都是什么意思呢？我们知道，\sqrt{V} 指的是一个簇所管辖的区间长度，所以 \operatorname{high}(x) 就表示了 x 这个数所在的簇的编号。显然 \operatorname{low}(x) 就表示了 x 这个数所在簇内部的编号。\operatorname{index}(x,y) 则表示了第 x 个簇中的第 y 个数所对应的编号。

注意：既然是向下取整，那么簇的编号肯定是从 0 开始的。

那么我们有一个很显然的等量关系：x=\operatorname{index}(\operatorname{high}(x),\operatorname{low}(x))。

原型 vEB 结构

我们可以像线段树那样采用递归分治的思想，从而建立一个树，不过这一次，一个父亲簇管辖的儿子簇的个数就不是 2 个了，而是 \sqrt{V} 个。同时，这个父亲簇会维护两个信息：其所管辖的区间长度以及一个 \operatorname{summary} 指针。

这样的父亲簇便形成了一种独特的结构，我们称其为原型 vEB 结构。对于一个区间长度为 V 的原型 vEB 结构，我们表示为：\operatorname{proto-vEB}(V)。（此处笔者在学习时，参考资料中说 \operatorname{proto-vEB}(V) 表示的是一个值域为 [0,V-1] 的原型 vEB 结构，笔者认为值域的说法有些委婉，故采用了更直接的“区间长度”这种说法。）

按上文所说，一个 \operatorname{proto-vEB}(V) 就应该管辖 \sqrt{V} 个 \operatorname{proto-vEB}(\sqrt{V})。也就是说其含有 \sqrt{V} 个指针指向更小的簇。

但是你一直递归下去，最后的区间长度会变成 2，这时候可没有更小的 \operatorname{proto-vEB}(\sqrt{2}) 给你管了，所以一个 \operatorname{proto-vEB}(2) 就直接管辖了其所对应的两个原来的桶数组的元素。我们将其称为基本结构。

那 \operatorname{summary} 指针是干什么用的呢？其指向了一个额外且特殊的 \operatorname{proto-vEB}(\sqrt{V})，这个 \operatorname{proto-vEB}(\sqrt{V}) 存储的是其它 \sqrt{V} 个 \operatorname{proto-vEB}(\sqrt{V}) 的所有信息的存在性的逻辑或。

是不是有点绕？总而言之，\operatorname{summary} 实际上就是辅助你去了解一个簇其所管辖的更小簇中是否有信息的东西。举个简单的例子：一个 \operatorname{proto-vEB(16)} 管辖了一个长度为 16 的区间，若其 \operatorname{summary} 的值为 0，则表示这一整个区间里面一个数都没有，而如果其值为 1，则表示这一整个区间里面至少存在 1 个数字。这样是不是好理解了一些。但是一定要注意：\operatorname{summary} 是一个指针，指向特殊的更小簇，而不是一个布尔类型的变量。同时对于一个基本结构，没有 \operatorname{summary}。

这个图可以帮助理解一个 \operatorname{proto-vEB}(V)：

我们便可以按照该结构递归进行建树了。

这样，由一堆原型 vEB 结构形成的树，我们称其为原型 vEB 树。

一个 V=16 的原型 vEB 树可以通过下图来表示：

（此图参考《算法导论》，笔者用不同颜色的线表示了部分 \operatorname{summary} 指针的指向关系。图表示的情况也已经标在了图里面。）

通过这张图，我们明显发现一个性质：对于一个数 x，其在不同簇里面的编号不一定相同。举个例子：5 这个数在基本结构里面和在 \operatorname{proto-vEB}(4) 里面的编号都为 0，可其在 \operatorname{proto-vEB}(16) 里面的编号为 4。（不要忘了编号是从 0 开始的）

一些操作实现（附代码）

本节以及 vEB 树一节的时间复杂度证明部分摘录于其他文章，其证明所引用的定理与摘录用的文章可见最后的“参考文献”一栏。

首先我们要定义出一个 \operatorname{proto-vEB}(V) 的结构体，以及三个基本的操作。

struct PROTO_vEB_tree {
    bool a[2];//基本结构
    vector<int>id;//管辖的节点的编号
    int V, summary_id;//区间长度以及特殊节点的编号
} node[100005];
inline int high(int id, int x) {
    return x / ((int)sqrt(node[id].V));
}
inline int low(int id, int x) {
    return x % ((int)sqrt(node[id].V));
}
inline int index(int id, int x, int y) {
    return x * ((int)sqrt(node[id].V)) + y;
}

时间复杂度的证明

后续的操作涉及两个递归式，这是两种不同的操作时间复杂度：

  1. T(V)=T(\sqrt{V})+O(1)

考虑变量替代法，令 m=\log V，则有 V=2^m，代入得：

T(2^m)=T(2^{\frac{m}{2}})+O(1)

重命名 S(m)=T(2^m)，则有：

S(m)=S(\frac{m}{2})+O(1)

根据 master 定理，解得 S(m)=O(\log m)，进行回代：

T(V)=T(2^m)=S(m)=O(\log m)=O(\log \log V)
  1. T(V)=2\times T(\sqrt{V})+O(1)

考虑变量替代法，令 m=\log V，则有 V=2^m，代入得：

T(2^m)=2\times T(2^\frac{m}{2})+O(1)

重命名 S(m)=T(2^m)，则有：

S(m)=2\times S(\frac{m}{2})+O(1)

根据 master 定理，解得 S(m)=O(m)，进行回代：

T(V)=T(2^m)=S(m)=O(m)=O(\log V)

我们再来看看问题：

  1. 判断数 x 是否存在于 S 中。

  2. 插入数 x 到 S 中，从 S 中删除数 x。

  3. 查询 S 的最大最小值。

  4. 询问 S 中一个数的前驱后继。

  1. 查询存在性。

我们直接递归访问即可：

bool check(int id,int x){
    if(node[id].V==2)return node[id].a[x];//查到了基本结构
    return check(node[id].id[high(id,x)],low(id,x));//继续往下递归
}

可以看见每次调用函数时只递归 1 次，符合第一个递归式，时间复杂度 O(\log \log n)。

当然，你值域都那么小了，直接访问原数组也没问题，这样子查询存在性就是 O(1)。

  1. 插入与删除操作。（插入时不保证存在性，删除时一定存在）

插入与删除略显复杂，因为涉及到 \operatorname{summary} 的改变，若删除后该簇内无元素，则需要将其对应的 \operatorname{summary} 元素赋值为 0，重点在于如何判断簇是否为空。我们可以引入一个变量 num 来表示当前簇内的元素个数。同时因为不保证插入时元素是否已经存在，还需要先判断存在性，以免重复累加数量。修改对应的 \operatorname{summary} 的操作可以在递归回溯时完成。注意，此处的 num 变量还要把 \operatorname{summary} 也统计进去。

以下是插入（不保证 x 的存在性）的代码：

int vEBT_insert(int id,int x){
    if(node[id].V==2){//进入了基本结构
        if(!node[id].a[x]){//该数不存在
            node[id].num_cnt++;//增加计数器
            node[id].a[x]=1;//赋值
            return 1;
        }
        return 0;
    }
    int cnt1=vEBT_insert(node[id].id[high(id,x)],low(id,x));//递归插入该元素
    int cnt2=vEBT_insert(node[id].summary_id,high(id,x));
    //因为插入时可能会把空簇变成有元素的簇，所以需要修改 summary
    //high(id,x) 是因为 summary 管辖的是簇的存在性，所以传递的是簇的编号
    node[node[id].id[high(id,x)]].num_cnt+=cnt1;
    node[node[id].summary_id].num_cnt+=cnt2;
    //在回传的过程中更新计数器
    return cnt1+cnt2;
}

为什么插入函数要有一个返回值呢？显然这是为了在回传的时候更方便地更新 num 的值。

我们再来看一下删除操作的代码实现：

int vEBT_delete(int id,int x){
    if(node[id].V==2){//进入基本结构 
        node[id].a[x]=0;
        --node[id].num_cnt;//赋值加减少一条龙服务 
        return 1;
    }
    int cnt1=vEBT_delete(node[id].id[high(id,x)],low(id,x));
    node[id].num_cnt-=cnt1;//计数器减少 
    if(!node[id].num_cnt){//如果说一整个簇全部空了 
        int cnt2=vEBT_delete(node[id].summary_id,high(id,x));//删除掉 summary 中对应的簇 
        node[node[id].summary_id].num_cnt-=cnt2;
    }
    return cnt1+cnt2;
}

那有人就会问了：“那要是题目不保证删除时 S 中有该元素呢？”删除之前调用一次查找函数即可，若查找不到该数直接跳过删除操作就行。

从最劣情况考虑，插入与删除均需要 2 次递归，符合递归式二，时间复杂度 O(\log n)。

  1. 查询最大最小值。

我们知道，在原型 vEB 结构中，元素是连续的，所以要查询最小值，只需要一直查询编号为 0 的簇即可，直到查询到基本结构，若 0 号元素存在，返回 0 号元素即可，若 0 号元素不存在但是 1 号元素存在，返回 1 号元素即可，若都不存在，则返回特殊值表示没有找到最小值。

但是这个思路对吗？显然不对。你一直查 0 号簇，最后查到的不就是 0 和 1 的存在性吗？要是最小值是 2 岂不是就错了。

你可能会说：没事，去查第一个有元素的簇不就好了。

要是我的最小值就是 V 呢？你这个复杂度岂不是飞上天了。

所以这个时候，\operatorname{summary} 的作用就体现出来了。前面在讲解的时候可能会有人怀疑：为什么 \operatorname{summary} 会是一个指针而不是一个布尔变量，维护区间或要什么指针啊。为了效率更高地去查询最大最小（以及后面的前驱后继），\operatorname{summary} 就是关键的一环。我们在查询最小值时，先去查询 \operatorname{summary} 看看这个簇里面有没有元素，如果没有则直接返回 -1。（因为 vEB 树存储的都是非负数，所以返回 -1 是很恰当的表示无最小值的方法，当然你也可以返回一个极大数，在值域以外就行）否则我们就沿着 \operatorname{summary} 一直查到基本结构去，然后返回 \operatorname{summary} 的最小值，这个最小值不是真正要查的最小值，而是最小值所在的簇的编号。这样子我们就巧妙地找出了最小值所在簇，随后回传编号并查普通簇就可以了。 查询最大值和最小值是差不多的，这里一并给出。

int vEBT_MIN(int id){
    if(node[id].V==2){
        if(node[id].a[0])return 0; 
        if(node[id].a[1])return 1;
        //因为本身就是有序的，所以优先 0 然后 1 
        return -1;
    }
    int min_id=vEBT_MIN(node[id].summary_id);//在 summary 里面获取最小值所在簇编号 
    if(min_id==-1)return -1;
    int min_num_id=vEBT_MIN(node[id].id[min_id]);//在最小值所在簇里面获取最小值编号 
    return index(id,min_id,min_num_id);//返回该最小值编号
}
int vEBT_MAX(int id){
    if(node[id].V==2){
        if(node[id].a[1])return 1;
        if(node[id].a[0])return 0;
        return -1;
    }//最大值就反着来，其他是一样的 
    int max_id=vEBT_MAX(node[id].summary_id);
    if(max_id==-1)return -1;
    int max_num_id=vEBT_MAX(node[id].id[max_id]);
    return index(id,max_id,max_num_id);
}

查询最大最小值操作需要递归 2 次，符合递归式二，时间复杂度 O(\log n)。

  1. 查询前驱与后继。

以前驱为例。进入基本结构后，如果该元素在基本结构内编号为 1 则且 0 号元素存在则直接返回 0 号元素。不是基本结构的话先看看往下找的簇是否非空，有元素就直接进去，否则去对应的 \operatorname{summary} 里面查有没有前驱簇，查到之后返回最大值即可。后继可类比得到。

int vEBT_Smaller_NUM(int id,int x){
    if(node[id].V==2){
        if(x==1&&node[id].a[0])return 0;
        return -1;
        //进基本结构直接找前驱 
    }
    int Smaller_NUM_id=vEBT_Smaller_NUM(node[id].id[high(id,x)],low(id,x));
    if(Smaller_NUM_id!=-1)return index(id,high(id,x),Smaller_NUM_id);//回传过来如果基本结构里面有前驱就返回编号 
    int Smaller_id=vEBT_Smaller_NUM(node[id].summary_id,high(id,x));//去 summary 里面找前驱簇 
    if(Smaller_id==-1)return -1;//找不到力（悲） 
    Smaller_NUM_id=vEBT_MAX(node[id].id[Smaller_id]);
    return index(id,Smaller_id,Smaller_NUM_id);
}
int vEBT_Bigger_NUM(int id,int x){
    if(node[id].V==2){
        if(x==0&&node[id].a[1])return 1;
        return -1;
        //找后继，实际上就是基本结构变了一下 
    }
    int Bigger_NUM_id=vEBT_Bigger_NUM(node[id].id[high(id,x)],low(id,x));
    if(Bigger_NUM_id!=-1)return index(id,high(id,x),Bigger_NUM_id);
    int Bigger_id=vEBT_Bigger_NUM(node[id].summary_id,high(id,x));
    if(Bigger_id==-1)return -1;
    Bigger_NUM_id=vEBT_MAX(node[id].id[Bigger_id]);
    return index(id,Bigger_id,Bigger_NUM_id);
}

这个操作的时间复杂度不太一样，最劣情况用了两次查询前驱后继和一次查询最大最小，时间复杂度为 O(\log n\log \log n)。

其递归式为：

T(V)=2\times T(\sqrt{V})+T(\log \sqrt{V})=2\times T(\sqrt{V})+O(\log V)

变量替代法，令 m= \log V，有：

T(2^m)=2\times T(2^{\frac{m}{2}})+O(m)

重命名 S(m)=T(2^m)，有：

S(m)=2\times S(\frac{m}{2})+O(m)

根据 master 定理解得 S(m)=O(m\log m)，则有：

T(V)=T(2^m)=S(m)=O(m\log m)=O(\log V\log\log V)

建树

讲了这么多，但是没讲原型 vEB 树的建树，因为这玩意实在没啥好讲的。你一个受值域限制，插入删除最大最小复杂度和平衡树一样，前驱后继复杂度比平衡树还大还不支持查排名的数据结构确实很鸡肋。有人用这东西只能说有点想不开，原型 vEB 树主要还是重在理解思路，为 vEB 树作铺垫的。

硬要建的话，仿照 vEB 树的建树整一个 O(V) 建树即可。注意这里不能使用 n 次插入，因为没有预处理出簇的指向关系，直接调用插入函数会导致越界 RE。

代码实现咕咕咕。

vEB 树

原型 vEB 树复杂度不够优秀，不过已经初现端倪，在查询以及删除的最优情况时可以达到 O(\log\log n)，我们来看看 vEB 树是怎么样的。

我们发现在原型 vEB 树一节中 V=\{2^{2^k}:k\in \mathbb{N}\} 的限制实在是太大了，我们把它变成 V=\{2^k:k\in \mathbb{N}\}，此时 \sqrt{V} 可能不再是整数。

我们记 \sqrt[\uparrow]{V}=2^{\lceil\frac{\log V}{2}\rceil}，\sqrt[\downarrow]{V}=2^{\lfloor\frac{\log V}{2}\rfloor}，故有 V=\sqrt[\uparrow]{V}\times \sqrt[\downarrow]{V}。我们对三个记号的定义也将发生一定的改变：

意思是没变的，只不过计算方式改了。

vEB 结构

同原型 vEB 树，vEB 树也是由 vEB 结构构成的，长的和原型 vEB 树也差不多。我们记一个大小为 V 的 vEB 结构为 \operatorname{vEB}(V)。

既然 \sqrt{V} 不保证是整数了，我们就要思考思考一个 \operatorname{vEB}(V) 里面是怎么样的。已知有 V=\sqrt[\uparrow]{V}\times \sqrt[\downarrow]{V}，且显然 \sqrt[\uparrow]{V}> \sqrt[\downarrow]{V}，不妨让 \operatorname{vEB}(V) 里面包含 \sqrt[\uparrow]{V} 个 \operatorname{vEB}(\sqrt[\downarrow]{V})，这样子可以减少单个簇内子簇的数量。由 \operatorname{summary} 的作用可知，\operatorname{summary} 指向一个 \operatorname{vEB}(\sqrt[\uparrow]{V})。当然这是针对非基础结构而言，基础结构还是只有 2 个元素且没有 \operatorname{summary} 指向更小簇。不过 vEB 结构比原型 vEB 结构多维护了一个 min 以及一个 max 标记。

既然如此，我们就可以取消掉基础结构中的两个 bool 变量了，取而代之的是最大最小值标记，因为你基础结构里面只有两个元素，不是最大就是最小。注意在基本结构里无元素时，min 与 max 要赋一个特殊值，比如说 -1。

同样的，我们有结构体定义：

map<int,int>lg;
struct vEB_Tree{
    int V,summary_id;
    vector<int>id;
    int max,min;
}node[100005];
inline void init(){
    for(int i=0;i<30;i++)lg[1<<i]=i;
}//因为定义变化，需要预处理 log
inline int high(int id,int x){
    int V=1<<(lg[node[id].V]>>1);
    return x/V;
}
inline int low(int id,int x){
    int V=1<<(lg[node[id].V]>>1);
    return x%V;
}
inline int index(int id,int x,int y){
    int V=1<<(lg[node[id].V]>>1);
    return x*V+y;
}

对于一颗 vEB 树，有以下性质：

具体地，我们对 min 与 max 进行分类讨论：

  • 若 min=max=-1，表示该簇内无元素。
  • 若 min=max\ge 0，表示该簇内有且仅有一个元素。
  • 若 min< max，表示该簇内至少有两个元素。
  • 若 min> max，说明你写错了。

建树预处理

vEB 树的建树不能单纯使用 n 次插入来建树，注意到我们使用的是 vector 作为管辖子簇的指针的，直接调用插入会导致越界 RE。当然你也可以用单纯的数组来实现管辖子簇的指针，但是这样空间会立即发生爆炸。

vEB 树的建树预处理和线段树不太一样，线段树在建树的同时就已经把原始数列插到树里面去了。vEB 树的预处理只是开点而已，后面还是得慢慢插。

由定义可知，一个 \operatorname{vEB}(V) 里面包含 \sqrt[\uparrow]{V} 个 \operatorname{vEB}(\sqrt[\downarrow]{V}) 以及一个 \operatorname{vEB}(\sqrt[\uparrow]{V})。按这个来建即可。

inline int get_siz(int n){
    int ret=0;
    while(1){
        if((1<<ret)>=n)return ret;
        ret++;
    }
}//获取树的大小
void build(int id,int siz){//2^siz
    node[id].summary_id=node[id].max=node[id].min=-1;
    if(siz<=1){
        node[id].V=2;
        return;
    }
    node[id].V=1<<siz;
    int children_siz=(siz>>1)+(siz&1);//ceil(log(V)/2)
    node[id].summary_id=++nodecnt;
    build(node[id].summary_id,children_siz);
    for(int i=0;i<(1<<children_siz);i++){
        node[id].id.emplace_back(++nodecnt);
        build(node[id].id[i],siz>>1);
    }
}

空间复杂度 O(V)，时间复杂度 O(V)，但是 vEB 树的节点个数比 V 要多，保险起见是开 2.5 倍空间，不过有时候 2 倍空间也够。

操作

vEB 树的所有操作都可以使用下面的递归式进行表示：

T(V)\le T(\sqrt[\uparrow]{V})+O(1)

令 m=\log V，有：

T(2^m)\le T(2^{\lceil\frac{m}{2}\rceil})+O(1)

我们注意到对于所有的 m\ge 2，都有 \lceil\frac{m}{2}\rceil\le \frac{2m}{3}，所以有：

T(2^m)\le T(2^{\frac{2m}{3}})+O(1)

重命名 S(m)=T(2^m)，有：

S(m)\le S(\frac{2m}{3})+O(1)

根据 master 定理解得 S(m)=O(\log m)，有：

T(V)=T(2^m)=S(m)=O(\log m)=O(\log\log V)
  1. 查询元素存在性

同样是递归调用，进入基本结构之后查元素存在性即可，不过这里可以进行一些小优化：若该元素等于簇中的最大值或最小值则直接返回，这样子如果查的刚好是最大值或者最小值常数复杂度会低一些，同时进入基本结构之后如果还没有返回，那就直接返回不存在，因为基本结构只有最大最小值，两个都不相等就说明不存在呗。

bool vEBT_Check(int id,int x){
    if(x==node[id].max||x==node[id].min)return 1;
    if(node[id].V==2)return 0;
    return vEBT_Check(node[id].id[high(id,x)],low(id,x));
}

使用了一次递归，时间复杂度 O(\log\log n)。

当然值域都这么小了，你开个桶也可以，O(1) 查询即可。

  1. 查询最大最小值。

直接返回根的最大最小值标记即可，时间复杂度 O(1)，我把这俩合一起写的。

inline int vEBT_MIN_or_MAX(int id,bool type){
    if(!type)return node[id].min;
    return node[id].max;
}
  1. 插入与删除一个数字。

首先我们要思考如何把插入的两次递归变成一次递归，在原型 vEB 树当中，我们不仅要递归进基本结构进行赋值，还需要递归进 \operatorname{summary} 进行赋值，如何解决该问题？

很简单，当一个簇非空时，其肯定已经存在于 \operatorname{summary} 当中，无需进行递归插入，而对于一个空簇，我们插入一个数就是给最大最小值直接赋值，可以 O(1) 搞定，一个簇变得非空之后肯定要插入 \operatorname{summary} 里面。注意到性质，min 是不存储于管辖的子簇里面的，所以我们没必要把 min 插进去，min 不插进去，说明子簇里面“没有数”，那么 max 也不插进去。所以我们直接就省去了插入子簇的操作，只是插入了 \operatorname{summary}，这样我们就把两次递归变成了一次，时间复杂度自然有了保证。这就是为什么 min 不存储于子簇当中的原因。

void vEBT_insert(int id,int x){
    if(node[id].min==-1){
        empty_insert(id,x);
        return;
    }
    if(x<node[id].min)swap(x,node[id].min);
    if(node[id].V>2){
        if(vEBT_MIN_or_MAX(node[id].id[high(id,x)],0)==-1){
            vEBT_insert(node[id].summary_id,high(id,x));
            empty_insert(node[id].id[high(id,x)],low(id,x));
        }else{
            vEBT_insert(node[id].id[high(id,x)],low(id,x));
        }
    }
    node[id].max=max(x,node[id].max);
}

注意一点，在插入的过程中，插入的数可能会成为新的最大最小值，需要进行判断。同时为了满足性质，我们在插入时，如果该数是新的最小值，那么需要与旧的最小值交换并插入旧的最小值。最大值在回传的时候更新即可。

那么接着来思考删除一个数。删除比插入稍微麻烦一点。

对于删除一个数，重点还是在于 \operatorname{summary} 的更新。显然当一个簇有且仅有一个数时进行删除操作才会导致 \operatorname{summary} 的更新。我们这里要对几种情况讨论一下。

进入基本结构后，若有两个元素，将最大最小值置反即可，若只有一个元素，则先将基本结构删空，然后回传，回传过程中看该簇是否已空，若空则在对应的 \operatorname{summary} 里面删掉该簇。但是这样会导致每回传一次就可能再递归进去删除一次，时间复杂度退化成了和原型 vEB 树一样的 O(\log n)。我们可以仿照插入的思路，在删除的过程中就进行判断，我们知道当 min=max 时，一整个簇里面有且仅有一个元素，而且既然递归到了这里，说明这个元素恰好是我们要删除的，我们直接 O(1) 修改 min 和 max 即可，随后不继续递归下去，直接进对应的 \operatorname{summary} 删掉该簇，全程只需一次递归，时间复杂度有了保证。

但是这只是删除普通元素的情况，我们还要考虑特殊元素，也就是删除的元素恰好为最大最小值的情况。此时我们除了上述操作之外还要去修改最大最小值标记。

先考虑删掉的是一个簇内的最小值，这个很好搞，因为根据性质，最小值不会存在其管辖的子簇里面，也就是说我们去查其管辖的簇里面的最小值，实际上就是查了这个簇的第二小值，我们用第二小值替换掉最小值即可，随后往下面删的时候删第二小值即可。查询最小值是 O(1) 的，时间复杂度可以保证。

再考虑删掉的是一个簇内的最大值，因为最大值是会下传的，我们考虑在回传的时候更新最大值。为什么要这样做呢？我们删掉了最大值后再去查询管辖的簇内的最大值，不就是查询到了第二大值了吗？随后我们把标记改成第二大值，就完成啦！

void vEBT_Delete(int id,int x){
    if(node[id].max==node[id].min){//只有一个元素
        node[id].max=node[id].min=-1;
        return;
    }
    if(node[id].V==2){
//进入基本结构里面，注意我们前面已经判断过只有一个元素的情况了
//这里肯定是有两个元素的情况
        node[id].max=node[id].min=!x;
        return;
    }
    if(x==node[id].min){
        int Min_Num_id=vEBT_MIN_or_MAX(node[id].summary_id,0);
        x=index(id,Min_Num_id,vEBT_MIN_or_MAX(node[id].id[Min_Num_id],0));
        node[id].min=x;
    }
    vEBT_Delete(node[id].id[high(id,x)],low(id,x));
    if(vEBT_MIN_or_MAX(node[id].id[high(id,x)],0)==-1){
        vEBT_Delete(node[id].summary_id,high(id,x));
        if(x==node[id].max){
            int Max_Num_id=vEBT_MIN_or_MAX(node[id].summary_id,1);//查的是第二大值
            if(Max_Num_id==-1)node[id].max=node[id].min;
//根据性质我们知道最小值不存在于管辖的簇中，所以第二大值为空时要把最小值赋值过去，就算最小值为空也要赋值
//第二大值为空，实际上就是说明整个簇只剩最小值了，也可能一点不剩
            else node[id].max=index(id,Max_Num_id,vEBT_MIN_or_MAX(node[id].id[Max_Num_id],1));
        }
    }else if(x==node[id].max)node[id].max=index(id,high(id,x),vEBT_MIN_or_MAX(node[id].id[high(id,x)],1));
}

删除操作涉及众多分类讨论，较为繁琐，建议多加阅读加强理解。

  1. 查询 x 的前驱后继。

我们仍然从优化原型 vEB 树的角度来看。

我们从后继开始讲起，前驱稍微麻烦一点点。首先是对于基本结构，我们直接套原型 vEB 树的处理方式就行，反正是 O(1) 的。那么当我们在基本结构里面没法 O(1) 查到后继又该怎么办呢？我们肯定不能学原型 vEB 树一样往上走一层去找后继，我们直接原地判断一波。如果 x 严格小于当前簇内的最小值，说明当前簇内最小值肯定就是 x 的后继了，直接返回。如果不满足这个条件，又不是基本结构，我们再来 O(1) 确定后继所在簇位置即可。但具体怎么确定呢？我们先查簇内有没有 x 的后继，具体来讲，先查簇内最大值，然后看 x 是否严格小于最大值，如果是，说明后继就在簇里面了，我们接着往下递归查子簇即可。如果 x 不是严格小于最大值，或者该簇内的最大值为空呢？我们就去 \operatorname{summary} 里面看有没有后继簇，如果有直接返回后继簇的最小值就可以了。经过这样子的分类讨论，我们成功确定了 x 的后继。

void vEBT_Successor(int id,int x){
    if(node[id].V==2){
        if(x==0&&node[id].max==1)return 1;
        return -1;
    }//此处与原型一致
    if(node[id].min!=-1&&x<node[id].min)return node[id].min;
    int SucNum_id;
    int maxid=vEBT_MIN_or_MAX(node[id].id[high(id,x)],1);//确定簇内最大值
    if(maxid!=-1&&low(id,x)<maxid){
        SucNum_id=vEBT_Successor(node[id].id[high(id,x)],low(id,x));//有最大值，去簇里面查
        return index(id,high(id,x),SucNum_id);
    }
    int Suc_id=vEBT_Successor(node[id].summary_id,high(id,x));//没最大值，去查后继簇
    if(Suc_id==-1)return -1;
    SucNum_id=vEBT_MIN_or_MAX(node[id].id[Suc_id],0);//后继簇最小值即为后继数
    return index(id,Suc_id,SucNum_id);
}

查前驱和后继基本是对称的，不过要注意，我们有性质，所以需要一条特判：我们找不到前驱簇，可能不是因为没有前驱，而是前驱没有存过来，我们要看看 min 是不是我们的前驱。

int vEBT_Predecessor(int id,int x){
    if(node[id].V==2){
        if(x==1&&node[id].min)return 0;
        return -1;
    }
    if(node[id].max!=-1&&x>node[id].max)return node[id].max;
    int PreNum_id;
    int preid=vEBT_MIN_or_MAX(node[id].id[high(id,x)],0);
    if(preid!=-1&&low(id,x)>preid){
        PreNum_id=vEBT_Predecessor(node[id].id[high(id,x)],low(id,x));
        return index(id,high(id,x),PreNum_id);
    }
    int Pre_id=vEBT_Predecessor(node[id].summary_id,high(id,x));
    if(Pre_id==-1){
        if(node[id].min!=-1&&x>node[id].min)return node[id].min;
        return -1;
    }
    PreNum_id=vEBT_MIN_or_MAX(node[id].id[Pre_id],1);
    return index(id,Pre_id,PreNum_id);
}

好！我们把四种操作讲完了。vEB 树，完结撒花！

Code

以模板题代码为例：（已格式化，放心食用）

#include <bits/stdc++.h>
#define ll long long
using namespace std;
inline ll read() {
    ll x = 0, w = 1;
    char ch = 0;

    while (ch < '0' || ch > '9') {
        if (ch == '-')
            w = -1;

        ch = getchar();
    }

    while (ch >= '0' && ch <= '9') {
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }

    return x * w;
}
inline void write(ll x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }

    static int sta[35];
    int top = 0;

    do {
        sta[top++] = x % 10, x /= 10;
    } while (x);

    while (top)
        putchar(sta[--top] + '0');

    putchar(' ');
}

int nodecnt;
map<int, int>lg;
struct vEB_Tree {
    int V, summary_id;
    vector<int>id;
    int max, min;
} node[1500000];
inline void init() {
    for (int i = 0; i < 32; i++)
        lg[1 << i] = i;
}
inline int high(int id, int x) {
    int V = 1 << (lg[node[id].V] >> 1);
    return x / V;
}
inline int low(int id, int x) {
    int V = 1 << (lg[node[id].V] >> 1);
    return x % V;
}
inline int index(int id, int x, int y) {
    int V = 1 << (lg[node[id].V] >> 1);
    return x * V + y;
}
inline int get_siz(int n) {
    int ret = 0;

    while (1) {
        if ((1 << ret) >= n)
            return ret;

        ret++;
    }
}
void build(int id, int siz) {
    node[id].summary_id = node[id].max = node[id].min = -1;

    if (siz <= 1) {
        node[id].V = 2;
        return;
    }

    node[id].V = 1 << siz;
    int children_siz = (siz >> 1) + (siz & 1);
    node[id].summary_id = ++nodecnt;
    build(node[id].summary_id, children_siz);
    node[id].id.resize(1 << children_siz);

    for (int i = 0; i < (1 << children_siz); i++) {
        node[id].id[i] = ++nodecnt;
        build(node[id].id[i], siz >> 1);
    }
}
bool vEBT_Check(int id, int x) {
    if (x == node[id].max || x == node[id].min)
        return 1;

    if (node[id].V == 2)
        return 0;

    return vEBT_Check(node[id].id[high(id, x)], low(id, x));
}
inline int vEBT_MIN_or_MAX(int id, bool type) {
    if (!type)
        return node[id].min;

    return node[id].max;
}
inline void empty_insert(int id, int x) {
    node[id].max = node[id].min = x;
}
void vEBT_insert(int id, int x) {
    if (node[id].min == -1) {
        empty_insert(id, x);
        return;
    }

    if (x < node[id].min)
        swap(x, node[id].min);

    if (node[id].V > 2) {
        if (vEBT_MIN_or_MAX(node[id].id[high(id, x)], 0) == -1) {
            vEBT_insert(node[id].summary_id, high(id, x));
            empty_insert(node[id].id[high(id, x)], low(id, x));
        } else {
            vEBT_insert(node[id].id[high(id, x)], low(id, x));
        }
    }

    node[id].max = max(x, node[id].max);
}
void vEBT_Delete(int id, int x) {
    if (node[id].max == node[id].min) {
        node[id].max = node[id].min = -1;
        return;
    }

    if (node[id].V == 2) {
        node[id].max = node[id].min = !x;
        return;
    }

    if (x == node[id].min) {
        int Min_Num_id = vEBT_MIN_or_MAX(node[id].summary_id, 0);
        x = index(id, Min_Num_id, vEBT_MIN_or_MAX(node[id].id[Min_Num_id], 0));
        node[id].min = x;
    }

    vEBT_Delete(node[id].id[high(id, x)], low(id, x));

    if (vEBT_MIN_or_MAX(node[id].id[high(id, x)], 0) == -1) {
        vEBT_Delete(node[id].summary_id, high(id, x));

        if (x == node[id].max) {
            int Max_Num_id = vEBT_MIN_or_MAX(node[id].summary_id, 1);

            if (Max_Num_id == -1)
                node[id].max = node[id].min;
            else
                node[id].max = index(id, Max_Num_id, vEBT_MIN_or_MAX(node[id].id[Max_Num_id], 1));
        }
    } else if (x == node[id].max)
        node[id].max = index(id, high(id, x), vEBT_MIN_or_MAX(node[id].id[high(id, x)], 1));
}
int vEBT_Successor(int id, int x) {
    if (node[id].V == 2) {
        if (x == 0 && node[id].max == 1)
            return 1;

        return -1;
    }

    if (node[id].min != -1 && x < node[id].min)
        return node[id].min;

    int SucNum_id;
    int maxid = vEBT_MIN_or_MAX(node[id].id[high(id, x)], 1);

    if (maxid != -1 && low(id, x) < maxid) {
        SucNum_id = vEBT_Successor(node[id].id[high(id, x)], low(id, x));
        return index(id, high(id, x), SucNum_id);
    }

    int Suc_id = vEBT_Successor(node[id].summary_id, high(id, x));

    if (Suc_id == -1)
        return -1;

    SucNum_id = vEBT_MIN_or_MAX(node[id].id[Suc_id], 0);
    return index(id, Suc_id, SucNum_id);
}
int vEBT_Predecessor(int id, int x) {
    if (node[id].V == 2) {
        if (x == 1 && node[id].min == 0)
            return 0;

        return -1;
    }

    if (node[id].max != -1 && x > node[id].max)
        return node[id].max;

    int PreNum_id;
    int preid = vEBT_MIN_or_MAX(node[id].id[high(id, x)], 0);

    if (preid != -1 && low(id, x) > preid) {
        PreNum_id = vEBT_Predecessor(node[id].id[high(id, x)], low(id, x));
        return index(id, high(id, x), PreNum_id);
    }

    int Pre_id = vEBT_Predecessor(node[id].summary_id, high(id, x));

    if (Pre_id == -1) {
        if (node[id].min != -1 && x > node[id].min)
            return node[id].min;

        return -1;
    }

    PreNum_id = vEBT_MIN_or_MAX(node[id].id[Pre_id], 1);
    return index(id, Pre_id, PreNum_id);
}
int n, m;
bool vis[1000005];
int main() {
    init();
    n = read();
    m = read();
    int siz = get_siz(n);
    build(0, siz);

    while (m--) {
        int op = read(), x;

        if (op == 1) {
            x = read();

            if (vis[x])
                continue;

            vis[x] = 1;
            vEBT_insert(0, x);
        }

        if (op == 2) {
            x = read();

            if (!vis[x])
                continue;

            vis[x] = 0;
            vEBT_Delete(0, x);
        }

        if (op == 3) {
            write(node[0].min);
            puts("");
        }

        if (op == 4) {
            write(node[0].max);
            puts("");
        }

        if (op == 5) {
            x = read();
            write(vEBT_Predecessor(0, x));
            puts("");
        }

        if (op == 6) {
            x = read();
            write(vEBT_Successor(0, x));
            puts("");
        }

        if (op == 7) {
            x = read();

            if (vis[x])
                cout << 1;
            else
                cout << -1;

            puts("");
        }
    }

    return 0;
}

一些温馨提示

  1. vEB 树适用于值域小，询问次数大的题目，如果值域过大，请尝试使用动态开点 vEB 树，但是如果把节点数开满了也会 MLE，空间复杂度 O(V) 是很大的问题。
  2. vEB 树的本质是多叉线段树，采用多次递归会导致常数较大，在能开辅助数组的情况下最好开辅助数组优化常数。
  3. vEB 树的无指针实现的空间常数极大，在值域 10^7 的情况下内存占用大约 1 GB ，如果时间宽松请尽量选择 Treap 等平衡树。

优化

主播主播，你的 vEBT 虽然时间复杂度很低，但是还是太吃常数了，局限性也大，有没有能减小常数的优化或者扩大维护范围的优化推荐一下。

有的兄弟，有的，像这样强势的优化，肯定是不止一个了，它们一共有六位，都是 vEBT 优化中 T0.5 的优化写法，掌握一到两个牢优化，你的常数至少能够减少三分之一，如果能全部掌握，可以直接减少一个数量级。

本节的优化代码会整合在一起放在最后。

动态开点

普通 vEBT 只能处理小值域的关键字，原因就在于 O(V) 的预处理复杂度以及 O(V) 的空间复杂度，虽然作为一个线段树中的异类中的异类，但是我们也要动态开点！

考虑直接丢掉预处理，所有的点在要用的时候再建立，考虑有 m 次操作，这样的空间复杂度就变成了 O(\min\{m\log \log V,V\})。

细讲一下动态开点：

不预处理加上大值域，最大的问题是可用的儿子的节点编号变得离散，vector 完全无法维护，所以需要使用哈希表来维护儿子编号，我直接使用了 unordered_map 维护，STL 不抽风的话是很好的选择，正确的选择是采用一种名为 Cuckoo Hashing 的哈希算法，我去简单看了一下相关文献，综合性能会更加优秀一些，链接会放在最后。

不预处理的第二个问题是对于一个节点无法直接查询其大小，需要通过父亲节点来进行确定，这个非常好搞，把节点大小作为函数参数下传即可，节点内直接不维护大小。

当然，这样的问题是：常数本来就大，然后 unordered_map 再给你加点料，你成功做到了 O(n\log \log n) 和 O(n\log n) 持平的复杂度。甚至可能还比人家更慢，空间还比人家更大，还不如去拿个 set 了事。

所以有必要加上一个很重要的优化，下文会阐述。

位运算优化

对于一个节点维护的大小 V，我们在普通 vEBT 中表示为 V=2^k。这导致我们在调用 \operatorname{high},\operatorname{low},\operatorname{index} 时需要预处理 \log，而且这三个核心函数是 vEBT 调用次数最多的函数，其中却包含了除法和取模两个耗费时间的运算。

我们将节点大小直接表示为 V=\log_2 2^k=k，可以直接省去 \log 数组的一丁点常数。

其次，因为节点大小必定为 2 的幂次，可以直接采用位运算代替除法，取模和乘法，降低运行时间。

常数并不会减少太多，但是这是通用卡常技巧，可以了解了解。

压位 vEBT

最重量级的一个优化。

对于一个节点大小为 2^6 的节点，我们要递归多少层到达基本结构呢？

2^6=2^3\times 2^3 2^3=2^2\times 2^1 2^2=2^1\times 2^1

是三层，而我们把它往上递归呢？

2^{12}=2^6\times 2^6 2^{24}=2^{12}\times 2^{12}

不用再往上递归了，可以看出：簇的大小越小，递归的时空开销就越不值得。你往上递归两次都已经碰到 10^7，这是普通 vEBT 的上界了，往下递归却要三次才能碰到下界？这太恶心了。

说到压位，大家可能第一个想到的就是 bitset 这个东西。其直接把 32 位的 01 信息压进一个 unsigned int 里面，常数瞬间减少了不知道多少。

我们可以做到更牛逼，注意到 2^6=64，而 unsigned long long 刚好是 64 位，二进制的下标刚刚好好是 0\sim 63。那还等什么？直接压进去啊！这样一来，我们直接把最小的簇大小从 2 提高到了 64，空间时间全省了不知道多少。因此关于几种操作也会有一定的变化：

  1. 查询一个数是否存在：

    状压 DP 的基础内容，不讲。

  2. 查询最小值：

    查找二进制数最靠前的 1 即可，手动写函数模拟的复杂度会不降反增，我们把目光放到 GNU 的内置函数里面。__builtin_ctzll 函数返回一个二进制数中前导零的个数，注意二进制数的低位在右边。其原型为 int __builtin_ctzll(unsigned long long)，时间复杂度高于 O(1) 但低于 O(\log n)，你也可以直接看成 O(1)，时间复杂度仍然是正确的。

  3. 查询最大值：

    寻找二进制数最靠后的 1 即可，GNU 提供内置函数 __builtin_clzll，返回一个二进制数中后导零的个数，原型为 int __builtin_clzll(unsigned long long)，注意求出后导零个数后要用位数减掉个数，不然是错的，时间复杂度同上。

  4. 插入一个数：

    状压 DP 的基础内容，不讲。

  5. 删除一个数：

    不保证删除的数的存在性，可以先用位运算进行判断，然后异或即可。判断和异或操作可以合在一起写。

  6. 查询前驱：

    设我们要查询第 x 个数的前驱，考虑将编号为 x\sim 63 的数全部剔除，然后转化为求最大值操作。剔除操作很简单，需要构造一个 0\sim x-1 位全部为 1，x\sim 63 位全部为 0 的二进制数并做按位与操作，构造的数字很好想，前驱就搞完了。

  7. 查询后继

    设我们要查询第 x 个数的后继，考虑将编号为 0\sim x 的数全部剔除，随后转化为查询最小值操作。构造一个 x+1\sim 63 位全部为 1，0\sim x 位全部为 0 的二进制数可行，但是太麻烦，可以直接整体右移 x+1 位，最后计算答案的时候再加上 x+1 即可。

以上所有操作记得判空，返回 -1。

常量引用

将函数中所有不会被修改的 int 替换为 const int&，减少一点点常数。这个是通用卡常技巧，可以用在任何函数里面。

支持可重复关键字

开一个数组记录关键字副本数，但是这样会无法使用动态开点。

vEBT 支持所有平衡树操作

在 \operatorname{vEB} 里面维护一个前缀数字个数，在查询时二分，即可支持查排名和查第 k 小值操作。但是时间复杂度是假的，会变成 O(\log n)，灵感来源：Butterfly_qwq。因为时间复杂度是假的所以没必要研究下去，故不给代码。

优化后代码：

动态开点，压位，位运算，常量引用优化，不支持重复关键字。

在值域 10^6，修改次数 2\times 10^6 的情况下（其实就是模板题）的最慢速度为 300 毫秒，内存 80 MB。相当恐怖的速度。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
mt19937 myrand(time(0));
inline ll read(){
    ll x=0,w=1;
    char ch=0;
    while(ch<'0'||ch>'9'){
        if(ch=='-')w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<3)+(x<<1)+(ch^48);
        ch=getchar();
    }
    return x*w;
}
void write(ll x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    static int sta[35];
    int top=0;
    do{
        sta[top++]=x%10,x/=10;
    }while(x);
    while(top)putchar(sta[--top]+'0');
}
const int N=1e6+5;
struct tree_node{
    int min,max,summary_id;
    unsigned ll V;
    unordered_map<int,int>id;
    tree_node(){min=max=-1;}
};
struct vEBT{
    tree_node node[N];
    int nodecnt;vEBT(){nodecnt=0;}
    inline int high(const int& V,const int& x){
        return x>>(V>>1);
    }
    inline int low(const int& V,const int& x){
        return x&((1<<(V>>1))-1);
    }
    inline int index(const int& V,const int& x,const int& y){
        return x<<(V>>1)|y;
    }
    int getmin(const int& id,const int& V){
        if(V<=6){
            return node[id].V?__builtin_ctzll(node[id].V):-1;
        }
        return node[id].min;
    }
    int getmax(const int& id,const int& V){
        if(V<=6){
            return node[id].V?63-__builtin_clzll(node[id].V):-1;
        }
        return node[id].max;
    }
    bool find(int &id,const int& V,const int& x){
        if(!id)id=++nodecnt;
        if(V<=6)return (node[id].V>>x&1);
        if(x==node[id].max||x==node[id].min)return 1;
        return find(node[id].id[high(V,x)],V>>1,low(V,x));
    }
    void insert(int &id,const int& V,int x){
        if(!id)id=++nodecnt;
        if(V<=6){
            node[id].V|=(1ull<<x);
            return;
        }
        if(node[id].min==-1){
            node[id].min=node[id].max=x;
            return;
        }
        if(x<node[id].min)swap(node[id].min,x);
        if(getmin(node[id].id[high(V,x)],V>>1)==-1)insert(node[id].summary_id,(V+1)>>1,high(V,x));
        insert(node[id].id[high(V,x)],V>>1,low(V,x));
        node[id].max=max(node[id].max,x);
    }
    void Delete(int &id,const int& V,int x){
        if(!id)id=++nodecnt;
        if(V<=6){
            node[id].V^=(node[id].V&(1ull<<x));
            return;
        }
        if(node[id].min==node[id].max){
            node[id].min=node[id].max=-1;
            return;
        }
        if(x==node[id].min){
            int Min_Num_id=getmin(node[id].summary_id,(V+1)>>1);
            x=index(V,Min_Num_id,getmin(node[id].id[Min_Num_id],V>>1));
            node[id].min=x;
        }
        Delete(node[id].id[high(V,x)],V>>1,low(V,x));
        if(getmin(node[id].id[high(V,x)],V>>1)==-1){
            Delete(node[id].summary_id,(V+1)>>1,high(V,x));
            if(x==node[id].max){
                int Max_Num_id=getmax(node[id].summary_id,(V+1)>>1);
                if(Max_Num_id==-1)node[id].max=node[id].min;
                else node[id].max=index(V,Max_Num_id,getmax(node[id].id[Max_Num_id],V>>1));
            }
        }else if(x==node[id].max)node[id].max=index(V,high(V,x),getmax(node[id].id[high(V,x)],V>>1));
    }
    int Predecessor(int &id,const int& V,const int& x){
        if(!id)id=++nodecnt;
        if(V<=6){
            int ret=-1;
            if(node[id].V&((1ull<<x)-1)){
                ret=63-__builtin_clzll(node[id].V&((1ull<<x)-1));
            }
            return ret;
        }
        if(node[id].max!=-1&&x>node[id].max)return node[id].max;
        int PreNum_id;
        int Min_id=getmin(node[id].id[high(V,x)],V>>1);
        if(Min_id!=-1&&low(V,x)>Min_id){
            PreNum_id=Predecessor(node[id].id[high(V,x)],V>>1,low(V,x));
            return index(V,high(V,x),PreNum_id);
        }
        int Pre_id=Predecessor(node[id].summary_id,(V+1)>>1,high(V,x));
        if(Pre_id==-1){
            if(node[id].min!=-1&&x>node[id].min)return node[id].min;
            return -1;
        }
        PreNum_id=getmax(node[id].id[Pre_id],V>>1);
        return index(V,Pre_id,PreNum_id);
    }
    int Successor(int &id,const int& V,const int& x){
        if(!id)id=++nodecnt;
        if(V<=6){
            int ret=-1;
            if(node[id].V>>(x+1)){
                ret=__builtin_ctzll(node[id].V>>(x+1));
                ret+=x+1;
            }
            return ret;
        }
        if(node[id].min!=-1&&x<node[id].min)return node[id].min;
        int SucNum_id;
        int Max_id=getmax(node[id].id[high(V,x)],V>>1);
        if(Max_id!=-1&&low(V,x)<Max_id){
            SucNum_id=Successor(node[id].id[high(V,x)],V>>1,low(V,x));
            return index(V,high(V,x),SucNum_id);
        }
        int Suc_id=Successor(node[id].summary_id,(V+1)>>1,high(V,x));
        if(Suc_id==-1)return -1;
        SucNum_id=getmin(node[id].id[Suc_id],V>>1);
        return index(V,Suc_id,SucNum_id);
    }
};
inline int get_siz(int n){
    int ret=0;
    while(1){
        if((1<<ret)>=n)return ret;
        ret++;
    }
}
vEBT tree;
int n,m,op,x,rt,maxv;
int main(){
    n=read();m=read();
    maxv=get_siz(n+1);
    while(m--){
        op=read();
        if(op==1){
            x=read();
            if(tree.find(rt,maxv,x))continue;
            tree.insert(rt,maxv,x);
        }
        if(op==2){
            x=read();
            if(!tree.find(rt,maxv,x))continue;
            tree.Delete(rt,maxv,x);
        }
        if(op==3){write(tree.getmin(rt,maxv));puts("");}
        if(op==4){write(tree.getmax(rt,maxv));puts("");}
        if(op==5){
            x=read();
            write(tree.Predecessor(rt,maxv,x));
            puts("");
        }
        if(op==6){
            x=read();
            write(tree.Successor(rt,maxv,x));
            puts("");
        }
        if(op==7){
            x=read();
            write(tree.find(rt,maxv,x)?1:-1);
            puts("");
        }
    }
    return 0;
}

后记

vEBT 的操作调用是一条链，所以说这东西可以可持久化。（正在科研中，以后会更新补上）

vEBT 的合并可以直接暴力合并，复杂度为 O(n\log \log n)，目前我并没有科研出复杂度低于此的合并方法。

另附其他 vEBT 的测试数据：

  1. 纯动态开点的 vEBT：

    在值域 10^6，修改次数 2\times 10^6 的情况下的最慢速度为 1500 毫秒，内存 180 MB。

  2. 普通 vEBT：

    在值域 10^6，修改次数 2\times 10^6 的情况下的最慢速度为 1100 毫秒，内存 80 MB。

所以说压位和动态开点最好一起用，不然常数比平衡树还大了。

习题

vEB 树确实很冷门，实在是找不到什么拓展题，找到的都是些板子。

黑暗爆炸3685

（板子）

Predecessor Problem

（这道题时限超级松到可以用 Treap，但是空间会特别紧张，为了练习还是自觉一点吧）

集合操作

（这道题有负数，整体偏移即可）

P2286 [HNOI2004] 宠物收养场

动态开点练习题。

参考文献

《算法导论》

你所不了解的数据结构-van Emde Boas 树

vanEmdeBoas树学习笔记

van Emde Boas Trees

An Overview of Cuckoo Hashing

重谈主定理（master定理）及其证明

特别鸣谢

排名不分先后。

Butterfly_qwq：提供了实现平衡树操作的思路。

RuntimeErr：提供了无指针写法，并提供了详细讲解。

LionBlaze：让我接触 vEBT 的人。

《算法导论》的作者们。

阅读到此处的你。