给你这样一个问题

有一个集合S，初始为空。然后有q次操作

操作有如下几种:

插入一个数，删除一个数，询问最大/最小值，询问一个数x的前驱/后继。

如果看到这个问题，你一定会想到平衡树，时间复杂度O(qlogn)。

但是，如果说，每个数在一个值域范围[0,u)中，是否会有更好的做法呢？

van♂树van Emde Boas 树就是这样一个数据结构，可以在O(u)预处理，O(loglogu)的时间复杂度处理每个操作。

这个在u不是很大而q比较大的时候比较有用。

首先，如果在一个值域[0,u)内处理这个问题，除了平衡树，你还会有什么方法？

一种方法是权值线段树，单次操作logu，这里不详细讲。

还有一种是分块，首先我们把序列分成\sqrt u块，定义a_i(值为0或1)，表示集合中是否有数i，定义summary_i表示第i个块内的值是否存在，就是把a_{i\sqrt u...(i+1)\sqrt u}或起来。

大致如下

图：{2,3,4,5,7,14,15}构建的

插入/删除 比较简单，只用修改一下a_i和summary即可

然后查询操作大概就是这样，以查前驱为例，首先在它所在的块查询，如果块内前面有a_i=1那么直接找；如果它所在的块前面都是0， 那么就上 summary查询，在summary上查找它所在块前面的第一个1所在块。

然后在这个块里找，找到块内最后面的一个a_i=1的位置，然后这个i就是它的前驱了。

其他的查询操作也类似。

时间复杂度单次操作O(\sqrt u)，似乎更慢了。

不过我们考虑一下，块内找，以及在summary上的查询，都是和原问题一样，只是规模变成了\sqrt u，变得更小的。

那么我们是否可以用一样的方法继续处理下去呢，就是对分块继续分块？

这就是vEB树的思想！

就像这样

好，现在对于vEB树，我们现在就有下面一个结构：

定义vEB(u)表示一个大小为u的vEB树

基础结构是vEB(2)，只存max和min

如果大小大于2，那么将会是如下结构

max,min存储vEB树中最大和最小的数，如果没有用/表示

一般情况下为了方便，我们设置u = 2^k,然后分块分为2^{\lceil k/2 \rceil }个块，每个块大小2^{\lfloor k/2 \rfloor }

然后是很重要的一点，就是min这个数在cluster中并不存储，这个性质很重要，将会是时间复杂度的保障。

大概就是这样

 (图源自算法导论) 建树的时空复杂度$T(u) = (\sqrt u+1)T(\sqrt u) = O(n)

好，现在我们开始操作。

一.求min/max

直接返回root的max/min即可

二.插入

比如说，我们现在要插入这么一个位置

那么现在有这么几种情况

1.插入所在块没有数

（此时max/min都不存在）

那么我们直接把max和min赋值成这个数即可

然后由于summary会被修改，所以我们就递归到summary继续修改即可

由于min并不存在于cluster中，所以我们就没必要在cluster递归下去

2.插入所在块有数

现在有这么两种情况

如果说，这个数x，小于min的话，我们把min改成x,然后由于min并不存在于cluster中，相当于我们还要把原来的min插入这个块中，递归下去即可

如果x>min ,那么相当于往块内插入一个x，同样的往cluster递归下去即可。

如果说x > max顺便更新一下max即可

然后我们分析一下时间复杂度，每次递归下去的话，规模就会变成原来的根号。

那么我们假设u = 2^{2^k}，那么递归下去一层规模就会变成\sqrt{2^{2^k}}=2^{2^{k-1}},所以我们会递归k层，每次操作时间复杂度即为O(k) = O(loglogu)

那么，这里我们也可以回答，为什么min往下存会错了。

假如一个空的位置，那么同一个点的summary和cluster都要修改。

单次查询复杂度 相当于是T(u) = 2T(\sqrt u)+1了，这个相当于T(2^k) = 2T(2^{\frac{k}{2}})+1 = O(k)，于是T(u)=O(logu)了，显然这个复杂度比O(loglogu)劣。

三、删除

这应该是vEB树里最复杂的一个了

假设我们删除如下位置的数

假如这个块只有一个数的话（max = min），那么直接把max和min设为不存在即可。然后由于summary修改了，所以我们只往summary递归下去就可以了。

假如这个块有多个数，下面分这么几种情况：

第一种，删的既不是max也不是min

没什么好说的，递归下去。

第二种，删的是min

现在相当于是把子块中的最小删掉了（因为min不在cluster中），并查询删完之后的最小值。

就像这样

但是子块的最小值我们不能直接知道。

不过我们可以先用A块的summary的min，找到第一个有1的子块（设它为B），然后B.min就是要删的了

然后我们可以往B递归下去了

同时我们必须更新A块的min

一样，我们再用A块的summary上的min(显然递归下去的时候summary也会被维护好的），找到那个块C之后答案就是C.min了

第三中，删max

和删min类似处理方式（不过这里子块的max不用重新找了）

复杂度分析

和插入一样T(u) = T(\sqrt u)+1 = O(loglogu)

四、前驱/后继

以求后继为例

现在我们求红箭头所指的位置的后继

现在有两种情况

1.后继在块内(用x <= max判定）

那么递归下去即可

查询前驱的话也类似，不过有个特点就是如果递归下去发现查不到前驱，那么它的前驱就是B.min（那个性质）

2.后继不在块内

这个相当于先求出B后面的第一个块，使得这个块内有数，那么答案就是这个块的min了。

那么怎么找到这个块？

就是在A的summary里找后继！

那么递归下去即可

找前驱在这里就完全对称了。

复杂度分析：

一样，每递归一层规模变为原来的根号

T(u) = T(\sqrt u)+1 = O(loglogu)