van Emde Boas 树——处理动态不可重前驱查询的利器

qhzx_FeS2_Butterfly

2024-10-22 21:28:45

Algo. & Theory

vEB 树——处理动态不可重前驱查询的利器

标题没说后继，但是是一样的。

vEB 树可以解决类平衡树问题，要求是元素无重复且值域不大（n\sim V），之后的复杂度分析会将 n 和 V 看做同阶（除第 5 节）。

代码在第 4 节自取。

引子——桶

考虑最朴素的方式——对数列开个桶，记录每一个元素是否存在，插删就是 O(1) 的，前驱后继查询直接遍历枚举，得到一个 O(n^2) 的复杂度。

0-1 Trie 与分块

前者在我的 vEB 树入门教程中说是建一个线段树，但是我感觉其实把他说是 0-1 trie 更恰当一点。

虽然 0-1 trie 就是个值域线段树。

但是这么说的话 vEB 树好像也就是个值域 Sqrt Tree（尽管在具体分块方案上有常数级别的差距）？

0-1 trie 维护前驱是 trival 的，直接看目前这一位：

如果标记为 1，尽量往 1 的方向走；
否则尽量往本位方向走，如果做不到的话就将标记置为 1。

时间复杂度为 O(n\log n)。

同样可以用类似的方法分块，时间复杂度为 O(n\sqrt{n})。

其中分块做法定义了“簇”的思想（之后再讲），很重要。

而我们延续下去的是这两种方法的结合。

proto-VEB 树

我们可以将值域补全为 2^{2^k} 形式，那么不仅 \sqrt{n} 是整数，\sqrt{\sqrt{n}}，\sqrt{\sqrt{\sqrt{n}}}，\sqrt{\sqrt{\sqrt{\sqrt{n}}}} 等也是整数。

先别急着说补全的时候可能把值域改成平方级别（如 n=65537 时）所以预处理承受不了，先看看后面的。

那么我们可以借鉴 Sqrt Tree 的思想，在分块里头，再套上分块！

注意不仅要对每个块内的信息维护一个小一点的 vEB（我们之后把这个东西称作“簇”），还要开一个小 vEB 代表每个元素里面有没有东西（我们之后把这个东西称作“汇总”）。

分析复杂度，判断存在是 O(\log \log n)，没问题，增删最大最小的话，——怎么是 O(\log n)？那和平衡树或 0-1 trie 有什么区别？

别急，先看看为什么是 \log 而不是 \log \log。

考虑增删的时候，不仅要增删对应簇，还要增删汇总。所以需要调用两次递归。所以就是 O(\log n)（证明不用在这里说了吧，主定理乱杀），最大最小同理。

查询前驱后继反而更慢，因为不仅要调用两次递归（可能是这个簇中的最大，但后缀在下个簇的最小值），还需要调用一次最小函数，时间复杂度为 O(\log n\log \log n)。

上面可不是废物算法，尽管比 0-1 trie 还要慢，但是和真正的 vEB 树已经很接近了。

真正的 vEB 树

真正的 vEB 树是这样维护的，我们不仅要记录大小、汇总和每个簇，还要记录最大值和最小值。并且最小值中维护的元素不会出现在任意一个簇中。

首先我们先把第一个坑填上：预处理时会做到 n^2。

考虑我们先不要求值域为 2^{2^k}，先把他补全为 2^k。

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

那么我们的汇总的大小变成了大小为 \sqrt[\uparrow]{n} 的 vEB 树，每个簇的大小都变成了 \sqrt[\downarrow]{n}。

接下来是操作讲解。

最大最小值直接 O(1) 查根节点就行了。

初始定义

struct node{int sz,mn,mx,smr;vector<int>ch;}vEB[N];
int dnsq(int u){return 1<<(lg[vEB[u].sz]>>1);}
int upsq(int u){return 1<<(lg[vEB[u].sz]+1>>1);}
int clus(int u,int x){return x/dnsq(u);}
int dnid(int u,int x){return x%dnsq(u);}
int upid(int u,int x,int y){return x*dnsq(u)+y;}

建树及判断元素是否存在

和 proto-vEB 几乎一样的部分。

int build(int u,int sz)
{
    vEB[u].sz=sz;
    vEB[u].mn=vEB[u].mx=-1;
    if(sz==2)return u;
    vEB[u].smr=build(++idx,upsq(u));
    for(int i=0;i<sz;i++)vEB[u].ch.push_back(build(++idx,dnsq(u)));
    return u;
}
bool find(int u,int x)
{
    if(vEB[u].mn==x||vEB[u].mx==x)return 1;
    if(vEB[u].sz==2)return 0;
    return find(vEB[u].ch[clus(u,x)],dnid(u,x));
}

查询元素后继和前驱

int succ(int u,int x)
{
    if(vEB[u].sz==2)
    {
        if(x==0&&vEB[u].mx==1)return 1;
        return NIL;
    }
    if(vEB[u].mn!=NIL&&x<vEB[u].mn)return vEB[u].mn;
    int tmp=vEB[vEB[u].ch[clus(u,x)]].mx;
    if(tmp!=NIL&&dnid(p,x)<tmp)return upid(u,clus(u,x),succ(vEB[u].ch[clus(u,x)],dnid(p,x)));
    int nxc=succ(vEB[u].smr,clus(u,x));
    if(nxc==NIL)return NIL;
    return upid(u,nxc,vEB[vEB[u].ch[nxc]].mn);
}
int pred(int u,int x)
{
    if(vEB[u].sz==2)
    {
        if(x==1&&vEB[u].mx==0)return 0;
        return NIL;
    }
    if(vEB[u].mx!=NIL&&x>vEB[u].mx)return vEB[u].mx;
    int tmp=vEB[vEB[u].ch[clus(u,x)]].mn;
    if(tmp!=NIL&&dnid(p,x)>tmp)return upid(u,clus(u,x),pred(vEB[u].ch[clus(u,x)],dnid(p,x)));
    int prc=pred(vEB[u].smr,clus(u,x));
    if(prc==NIL)
    {
        if(vEB[u].mn!=NIL&&x>vEB[u].mn)return vEB[u].mn
        return NIL;
    }
    return upid(u,prc,vEB[vEB[u].ch[prc]].mn);
}

后继就是先找在自己这个簇的后缀，如果没有就找这个簇在汇总中的后缀，都没有就是 NIL。

前驱基本对称，大家可以找找不同。

不同之处在于注意最小值是不存在后面的簇里的，所以需要判掉。

插入元素

void insert(int u,int x)
{
    if(vEB[u].mn==NIL)
    {
        vEB[u].mn=vEB[u].mx=x;
        return;
    }
    if(x<vEB[u].mn)swap(x,vEB[u].mn);
    if(vEB[u].sz>2)
    {
        int tmp=vEB[u].ch[clus(u,x)];
        if(vEB[tmp].mn==NIL)
        {
            insert(vEB[u].smr,clus(u,x));
            vEB[tmp].mn=vEB[tmp].mx=dnid(u,x);
        }
        else insert(tmp,dnid(u,x));
    }
    vEB[u].mx=max(vEB[u].mx,x);
}

传统的两次递归显然是不能满足我们的复杂度了。

这时候我们要记一个神秘的不下传的最小值的原因就要体现出来了，如果簇为空，可以 O(1) 放到最小值里，然后再把簇插入到汇总里，否则的话汇总就不用动，把元素插入到簇里即可。

删除元素

void del(int u,int x)
{
    if(vEB[u].mn==vEB[u].mx)
    {
        vEB[u].mn=vEB[u].mx=NIL;
        return;
    }
    if(vEB[u].sz==2)
    {
        vEB[u].mn=vEB[u].mx=!x;
        return;
    }
    if(x==vEB[u].mn)vEB[u].mn=x=upid(u,vEB[vEB[u].smr].mn,vEB[vEB[u].ch[vEB[vEB[u].smr].mn]].mn);
    del(vEB[u].ch[clus(u,x)],dnid(u,x));
    if(vEB[vEB[u].ch[clus(u,x)]].mn==NIL)
    {
        del(vEB[u].smr,clus(u,x));
        if(x==vEB[u].mx)
        {
            if(vEB[vEB[u].smr].mx==NIL)vEB[u].mx=vEB[u].mn;
            else vEB[u].mx=upid(u,vEB[vEB[u].smr].mx,vEB[vEB[u].ch[vEB[vEB[u].smr].mx]].mx);
        }
    }
    else if(x==vEB[u].mx)vEB[u].mx=upid(u,clus(u,x),vEB[vEB[u].ch[clus(u,x)]].mx);
}

最难的一个操作。

注意这个函数需要保证删除元素存在。

如果只有一个元素就直接删，大小为 2 就删一个。

如果删除的是最小值就把最小值改成次小值，然后删除次小值，删除的是最大值同理。

然后往下删除，如果为空就删汇总。

注意到如果删了汇总的话删簇的时候一定是 O(1) 的，所以复杂度是正确的。

完整代码

代码所对应的题面为这个。

#include<bits/stdc++.h>
using namespace std;
const int NIL=-1,N=2000005;
int q,v,idx=1,l[N];
struct node{int sz,mn,mx,smr;vector<int>ch;}vEB[N];
int dnsq(int u){return 1<<(l[vEB[u].sz]>>1);}
int upsq(int u){return 1<<(l[vEB[u].sz]+1>>1);}
int clus(int u,int x){return x/dnsq(u);}
int dnid(int u,int x){return x%dnsq(u);}
int upid(int u,int x,int y){return x*dnsq(u)+y;}
int build(int u,int sz)
{
    vEB[u].sz=sz;
    vEB[u].mn=vEB[u].mx=-1;
    if(sz==2)return u;
    vEB[u].smr=build(++idx,upsq(u));
    for(int i=0;i<sz;i++)vEB[u].ch.push_back(build(++idx,dnsq(u)));
    return u;
}
bool find(int u,int x)
{
    if(vEB[u].mn==x||vEB[u].mx==x)return 1;
    if(vEB[u].sz==2)return 0;
    return find(vEB[u].ch[clus(u,x)],dnid(u,x));
}
int succ(int u,int x)
{
    if(vEB[u].sz==2)
    {
        if(x==0&&vEB[u].mx==1)return 1;
        return NIL;
    }
    if(vEB[u].mn!=NIL&&x<vEB[u].mn)return vEB[u].mn;
    int tmp=vEB[vEB[u].ch[clus(u,x)]].mx;
    if(tmp!=NIL&&dnid(u,x)<tmp)return upid(u,clus(u,x),succ(vEB[u].ch[clus(u,x)],dnid(u,x)));
    int nxc=succ(vEB[u].smr,clus(u,x));
    if(nxc==NIL)return NIL;
    return upid(u,nxc,vEB[vEB[u].ch[nxc]].mn);
}
int pred(int u,int x)
{
    if(vEB[u].sz==2)
    {
        if(x==1&&vEB[u].mx==0)return 0;
        return NIL;
    }
    if(vEB[u].mx!=NIL&&x>vEB[u].mx)return vEB[u].mx;
    int tmp=vEB[vEB[u].ch[clus(u,x)]].mn;
    if(tmp!=NIL&&dnid(u,x)>tmp)return upid(u,clus(u,x),pred(vEB[u].ch[clus(u,x)],dnid(u,x)));
    int prc=pred(vEB[u].smr,clus(u,x));
    if(prc==NIL)
    {
        if(vEB[u].mn!=NIL&&x>vEB[u].mn)return vEB[u].mn;
        return NIL;
    }
    return upid(u,prc,vEB[vEB[u].ch[prc]].mn);
}
void insert(int u,int x)
{
    if(vEB[u].mn==NIL)
    {
        vEB[u].mn=vEB[u].mx=x;
        return;
    }
    if(x<vEB[u].mn)swap(x,vEB[u].mn);
    if(vEB[u].sz>2)
    {
        int tmp=vEB[u].ch[clus(u,x)];
        if(vEB[tmp].mn==NIL)
        {
            insert(vEB[u].smr,clus(u,x));
            vEB[tmp].mn=vEB[tmp].mx=dnid(u,x);
        }
        else insert(tmp,dnid(u,x));
    }
    vEB[u].mx=max(vEB[u].mx,x);
}
void del(int u,int x)
{
    if(vEB[u].mn==vEB[u].mx)
    {
        vEB[u].mn=vEB[u].mx=NIL;
        return;
    }
    if(vEB[u].sz==2)
    {
        vEB[u].mn=vEB[u].mx=!x;
        return;
    }
    if(x==vEB[u].mn)vEB[u].mn=x=upid(u,vEB[vEB[u].smr].mn,vEB[vEB[u].ch[vEB[vEB[u].smr].mn]].mn);
    del(vEB[u].ch[clus(u,x)],dnid(u,x));
    if(vEB[vEB[u].ch[clus(u,x)]].mn==NIL)
    {
        del(vEB[u].smr,clus(u,x));
        if(x==vEB[u].mx)
        {
            if(vEB[vEB[u].smr].mx==NIL)vEB[u].mx=vEB[u].mn;
            else vEB[u].mx=upid(u,vEB[vEB[u].smr].mx,vEB[vEB[u].ch[vEB[vEB[u].smr].mx]].mx);
        }
    }
    else if(x==vEB[u].mx)vEB[u].mx=upid(u,clus(u,x),vEB[vEB[u].ch[clus(u,x)]].mx);
}
int main()
{
    cin>>q>>v;
    for(int i=1;;i<<=1)if(i>=v){v=i;break;}
    for(int i=2;i<=v;i++)l[i]=l[i>>1]+1;
    build(1,v);
    for(int i=1,op,x;i<=q;i++)
    {
        cin>>op;
        if(op==1)
        {
            cin>>x;
            if(!find(1,x))insert(1,x);
        }
        if(op==2)
        {
            cin>>x;
            if(find(1,x))del(1,x);
        }
        if(op==3)
        {
            cin>>x;
            if(find(1,x))cout<<"1\n";
            else cout<<"0\n";
        }
        if(op==4)
        {
            cin>>x;
            cout<<pred(1,x)<<'\n';
        }
        if(op==5)
        {
            cin>>x;
            cout<<succ(1,x)<<'\n';
        }
        if(op==6)cout<<vEB[1].mn<<'\n';
        if(op==7)cout<<vEB[1].mx<<'\n';
    }
}

但是你如果把代码放到本地测发现事实上跑超过 100ms 了，原因是输入输出太慢了。

所以建议加个 fread，在 vEB 里面卡卡常，就差不多可以过去。

动态开点 vEB 树

vEB 树有一个 O(V) 的预处理怎么办？

这样顶着个亚 log 数据结构的名称复杂度里有个线性值域？

不行，必须消掉啊！

考虑直接不管预处理，需要用的时候再开点，就是动态开点任何树的核心。

显然一次最多开 O(\log \log V) 个点，那么时间复杂度为 O(n\log\log V)，空间复杂度为 O(\min\{V,n\log\log V\})。

由于是动态开点，所以所有操作都要记个父亲用于开点的时候拿 sz。除了判断存在以外，记得再开个变量记录这是汇总还是簇。

但是你都 vEB 了放个 10^9 值域其实挺无聊的，所以就不给代码了。