vanEmdeBoas树学习笔记

给你这样一个问题 有一个集合$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中并不存储，这个性质很重要，将会是时间复杂度的保障。 大概就是这样 $u = 16$，$S=${$2,3,4,5,7,14,15$}的vEB树  (图源自算法导论) 建树的时空复杂度$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)$