专栏文章

vanEmdeBoas树学习笔记

YYnoi
算法·理论参与者 47已保存评论 51

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
51 条
当前快照
1 份
快照标识符
@mhz5svs9
此快照首次捕获于
2025/11/15 01:56
4 个月前
此快照最后确认于
2025/11/29 05:24
3 个月前
查看原文
给你这样一个问题
有一个集合SS，初始为空。然后有qq次操作
操作有如下几种:
插入一个数，删除一个数，询问最大/最小值，询问一个数xx的前驱/后继。
如果看到这个问题，你一定会想到平衡树，时间复杂度O(qlogn)O(qlogn)。
但是，如果说，每个数在一个值域范围[0,u)[0,u)中，是否会有更好的做法呢？
van♂树van Emde Boas 树就是这样一个数据结构，可以在O(u)O(u)预处理，O(loglogu)O(loglogu)的时间复杂度处理每个操作。
这个在uu不是很大而qq比较大的时候比较有用。
首先，如果在一个值域[0,u)[0,u)内处理这个问题，除了平衡树，你还会有什么方法？
一种方法是权值线段树，单次操作logulogu，这里不详细讲。
还有一种是分块，首先我们把序列分成u\sqrt u块，定义aia_i(值为00或11)，表示集合中是否有数ii，定义summaryisummary_i表示第ii个块内的值是否存在，就是把aiu...(i+1)ua_{i\sqrt u...(i+1)\sqrt u}或起来。
大致如下
图：{2,3,4,5,7,14,152,3,4,5,7,14,15}构建的
插入/删除 比较简单，只用修改一下aia_i和summarysummary即可
然后查询操作大概就是这样，以查前驱为例，首先在它所在的块查询，如果块内前面有ai=1a_i=1那么直接找；如果它所在的块前面都是00， 那么就上 summarysummary查询，在summarysummary上查找它所在块前面的第一个11所在块。
然后在这个块里找，找到块内最后面的一个ai=1a_i=1的位置，然后这个ii就是它的前驱了。
其他的查询操作也类似。
时间复杂度单次操作O(u)O(\sqrt u)，似乎更慢了。
不过我们考虑一下，块内找，以及在summarysummary上的查询，都是和原问题一样，只是规模变成了u\sqrt u，变得更小的。
那么我们是否可以用一样的方法继续处理下去呢，就是对分块继续分块？
这就是vEB树的思想！
就像这样
好，现在对于vEB树，我们现在就有下面一个结构：
定义vEB(u)vEB(u)表示一个大小为uu的vEB树
基础结构是vEB(2)vEB(2)，只存max和min
如果大小大于22，那么将会是如下结构
max,min存储vEB树中最大和最小的数，如果没有用//表示
一般情况下为了方便，我们设置u=2ku = 2^k,然后分块分为2⌈k/2⌉2^{\lceil k/2 \rceil }个块，每个块大小2⌊k/2⌋2^{\lfloor k/2 \rfloor }
然后是很重要的一点，就是minmin这个数在cluster中并不存储，这个性质很重要，将会是时间复杂度的保障。
大概就是这样
u=16u = 16，S=S={2,3,4,5,7,14,152,3,4,5,7,14,15}的vEB树
(图源自算法导论)
建树的时空复杂度T(u)=(u+1)T(u)=O(n)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.插入所在块有数

现在有这么两种情况
如果说，这个数xx，小于min的话，我们把min改成xx,然后由于min并不存在于cluster中，相当于我们还要把原来的min插入这个块中，递归下去即可
如果x>minx>min ,那么相当于往块内插入一个xx，同样的往cluster递归下去即可。
如果说x>maxx > max顺便更新一下maxmax即可
然后我们分析一下时间复杂度，每次递归下去的话，规模就会变成原来的根号。
那么我们假设u=22ku = 2^{2^k}，那么递归下去一层规模就会变成22k=22k−1\sqrt{2^{2^k}}=2^{2^{k-1}},所以我们会递归k层，每次操作时间复杂度即为O(k)=O(loglogu)O(k) = O(loglogu)
那么，这里我们也可以回答，为什么min往下存会错了。
假如一个空的位置，那么同一个点的summarysummary和clustercluster都要修改。
单次查询复杂度 相当于是T(u)=2T(u)+1T(u) = 2T(\sqrt u)+1了，这个相当于T(2k)=2T(2k2)+1=O(k)T(2^k) = 2T(2^{\frac{k}{2}})+1 = O(k)，于是T(u)=O(logu)T(u)=O(logu)了，显然这个复杂度比O(loglogu)O(loglogu)劣。

三、删除

这应该是vEB树里最复杂的一个了
假设我们删除如下位置的数
假如这个块只有一个数的话（max = min），那么直接把max和min设为不存在即可。然后由于summary修改了，所以我们只往summary递归下去就可以了。
假如这个块有多个数，下面分这么几种情况：
第一种，删的既不是max也不是min
没什么好说的，递归下去。
第二种，删的是minmin
现在相当于是把子块中的最小删掉了（因为min不在cluster中），并查询删完之后的最小值。
就像这样
但是子块的最小值我们不能直接知道。
不过我们可以先用A块的summarysummary的minmin，找到第一个有11的子块（设它为B），然后B.min就是要删的了
然后我们可以往BB递归下去了
同时我们必须更新A块的minmin
一样，我们再用A块的summarysummary上的minmin(显然递归下去的时候summarysummary也会被维护好的），找到那个块CC之后答案就是C.minC.min了
第三中，删maxmax
和删minmin类似处理方式（不过这里子块的maxmax不用重新找了）
复杂度分析
和插入一样T(u)=T(u)+1=O(loglogu)T(u) = T(\sqrt u)+1 = O(loglogu)

四、前驱/后继

以求后继为例
现在我们求红箭头所指的位置的后继
现在有两种情况
1.后继在块内(用x<=maxx <= max判定）
那么递归下去即可
查询前驱的话也类似，不过有个特点就是如果递归下去发现查不到前驱，那么它的前驱就是B.minB.min（那个性质）
2.后继不在块内
这个相当于先求出B后面的第一个块，使得这个块内有数，那么答案就是这个块的minmin了。
那么怎么找到这个块？
就是在AA的summarysummary里找后继！
那么递归下去即可
找前驱在这里就完全对称了。
复杂度分析：
一样，每递归一层规模变为原来的根号
T(u)=T(u)+1=O(loglogu)T(u) = T(\sqrt u)+1 = O(loglogu)

评论

共 51 条评论，欢迎与作者交流。

正在加载评论...