Aqours 树 —— wblt 的替代品

_Ch1F4N_ · 2024-07-06 02:27:28 · 科技·工程

前言

原文

膜拜神 @DaydreamWarrior

概述

Aqours 树是一种 2-3 leafy 树，具体而言，只有叶子节点维护了元素，其他的节点都只用来检索，其他的节点均只有 2 个儿子或者 3 个儿子，对于每个节点有一个区间 [l,r] 表示子树内的叶子值域范围，对于一个点的所有儿子节点的区间按照右端点排序后相邻两个区间 至多 有一个公共点。并且 Aqours 树上所有叶子节点深度相同。

那么平衡树的基本操作如第 k 大，求排名等运用这个索引结构可以轻松地求出。

合并

这里指的是值域不交的合并。

假设我们合并两棵 Aqours 树 x,y，不妨假设 height(x) \leq height(y)，首先在树 y 上应该被放入的节点，具体地，以将 x 插入 y 的最左侧为例，我们在树 y 上一直向左走，知道一个点的深度满足将 x 接到他的儿子中整棵树依然满足每个叶子深度相同一性质。

假设要把树 x 个根 rt_x 作为点 u 的一个儿子。

假若 u 是二叉的，那么十分简单，改成三叉，也就是增加一个最左边的儿子或者最右边的儿子将原来的儿子向左或者向右平移一下位置即可。

否则，u 是三叉的，我们拆下 u 最左边或者最右边一叉 z，新建一个点 g 使其的儿子分别为 rt_x 与 z。

注意到 height(sub_g) = height(x) + 1，也就是此时以 g 为根的子树应当接到 u 的父亲 fa_u 上，这个时候我们发现把 sub_g 接到 fa_u 的儿子上的过程与把 x 接到 u 的儿子上相似，因此直接向上递归求解即可。

如果递归到了根，那么再次新建一个节点 r 将原来的根与递归上来的新子树分别作为其的两个儿子即可。

令人惊讶的是，这个过程并非简单的 O(\log n) 而是 O(height(y) - height(x)) 也就是 O(\log sz_y - \log sz_x)。

并且得到的新树树高 \in [height(y),height(y)+1]。

分裂

假若要分裂成 [-\infty,v] 与 (v,\infty]。

首先在 Aqours 树上检索 v 或者说找到所有满足其代表值域范围会被分裂分成两个值域范围的节点，由于这个操作与检索 v 类似，因此满足条件的节点一定是从根到叶子的一条链。

我们将这条链上所有点拆开，也就是将这些点与其儿子的边全部断开。

那么剩下这条链上的一些点和这些点的儿子的子树，对于链上的拆分后孤立的非叶子节点，由于其已经没有了检索价值，直接丢掉，然后对于剩下的子树，一定是若干棵 Aqours 树（我们认为链上的叶子节点拆分完后变为一个单独的代表信息的叶子节点也算一棵 Aqours 树），由于你是从上往下拆，所以拆出来的 Aqours 树高度递减，将这些树按照全树小于等于 v 与大于 v 分类（跨过 v 的不存在，因为那些已经被拆掉了），然后每种类别内按照高度从小往大依次合并。

分析下复杂度，假若对于一个类别内子树 height 分别为 a_1,a_2,...,a_k 那么在合并的过程中复杂度就是 O(\sum a_{i} - a_{i-1} + \sum C) = O(a_k - a_1 + \sum C) = O(\log n + \sum C) 这里 C 代表的是由于合并后 height 增加带来的影响，但是你发现 height 增加的前提是树 y 的根节点为三叉节点，而一次树高增加后根节点是二叉节点，所以一次树高增加后至少再一次合并才会使得树高再次增加，而又因为 a 序列中至多又两个相同的不为 1 的值（第三个相同高度的儿子一定被分裂开来了，除非是叶子，然而叶子的高度为 1）因此合并过程中，令 \Delta a_{i-1} 表示合并到第 i-1 棵子树时合并带来的树高变化量，有 合并完叶子后任意时刻 \Delta a_{i-1} 的增长量不大于 a_i 的增长量加 1（因为一种 a_i 至多两个引发一次树高增加后必定引起一次 a_i 增加，也就是遍历到了新的 a_i） 且 \Delta a_{i-1},a_i 在刚合并完叶子后均为常数（叶子大小为 1 且至多 3 个），又因为至多 3 次合并大小为 1 的叶子节点复杂度是一个常数，而整个过程中 \max(C) = \max(0,\max(\Delta a_{i-1} - a_{i})) 也是个常数，所以总的复杂度仍然是 O(\log n)。

性质

所有叶子等深度（树高较小）。重量平衡，即父亲的子树大小至少是儿子的 1+c（其中 c 是正常数）倍。

相比于 wblt

貌似可以胜任同样的工作。

听发明者说他实现的版本比 wblt 更快。

实现

我实现的比较劣，常数较大。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6+1e5+114;
struct Aqours_Tree{
    int s[3];
    int r;
    int sz,height;
    Aqours_Tree(){
        sz=s[0]=s[1]=s[2]=0;
        r=INT_MAX;
        height=1;
    }
}tr[maxn<<1];
int tot;
int trash[maxn<<1];
int st;
inline int clone(){
    if(st>0){
        int New=trash[st];
        st--;
        tr[New]=Aqours_Tree();
        return New;
    }
    else return ++tot;
}
inline void pushup(int u){
    if(tr[u].s[0]==0) return ;
    tr[u].sz=tr[tr[u].s[0]].sz+tr[tr[u].s[2]].sz+tr[tr[u].s[1]].sz;
    tr[u].r=tr[tr[u].s[1]].r;
    tr[u].height=tr[tr[u].s[0]].height+1;
}
int father[60],cntf;
int Tmerge(int x,int u,int T){
    while(1){
        if(tr[u].s[2]==0){
            tr[u].s[2]=tr[u].s[T];
            tr[u].s[T]=x;
            while(cntf>0) pushup(father[cntf]),cntf--;
            return father[1];
        }
        else{
            int g=clone();
            tr[g].s[T]=x,tr[g].s[T^1]=tr[u].s[T];
            pushup(g);
            tr[u].s[T]=tr[u].s[2];
            tr[u].s[2]=0;
            pushup(u);
            if(cntf==1){
                int f=clone();
                tr[f].s[T]=g,tr[f].s[T^1]=u;
                tr[f].s[2]=0;
                pushup(f);
                return f;
            }else{
                x=g;
                u=father[--cntf];
            }
        }
    }
}
int merge(int u,int v){
    if(u==0||v==0) return u+v;
    if(tr[u].height==tr[v].height){
        int g=clone();
        tr[g].s[0]=u,tr[g].s[1]=v;
        pushup(g);
        return g;
    }else if(tr[u].height>tr[v].height){
        cntf=0;
        while(tr[u].height>tr[v].height+1){
            father[++cntf]=u;
            u=tr[u].s[1];
        }
        father[++cntf]=u;
        int res=Tmerge(v,u,1);
        return res;
    }else{
        cntf=0;
        while(tr[v].height>tr[u].height+1){
            father[++cntf]=v;
            v=tr[v].s[0];
        }
        father[++cntf]=v;
        int res=Tmerge(u,v,0);
        return res;
    }
}
int X[60],Y[60],totX,totY;
void split(int u,int &x,int &y,int v){
    if(u==0){
        x=y=0;
        return ;
    }
    x=0,y=0;
    totX=totY=0;
    while(tr[u].s[0]!=0){
        int x=tr[u].s[0],y=tr[u].s[2],z=tr[u].s[1];
        trash[++st]=u;
        if(v<tr[tr[u].s[0]].r){
            Y[++totY]=tr[u].s[1];
            Y[++totY]=tr[u].s[2];
            u=tr[u].s[0];
        }else if(tr[u].s[2]!=0&&v<tr[tr[u].s[2]].r){
            X[++totX]=tr[u].s[0];
            Y[++totY]=tr[u].s[1];
            u=tr[u].s[2];
        }else{
            X[++totX]=tr[u].s[0];
            X[++totX]=tr[u].s[2];
            u=tr[u].s[1];
        }
    }
    if(tr[u].r<=v) X[++totX]=u;
    else Y[++totY]=u;
    for(int i=totX;i>=1;i--) x=merge(X[i],x);
    for(int i=totY;i>=1;i--) y=merge(y,Y[i]);
}
int kth(int u,int k){
    while(tr[u].s[0]!=0){
        if(k<=tr[tr[u].s[0]].sz) u=tr[u].s[0];
        else{
            k-=tr[tr[u].s[0]].sz;
            if(k<=tr[tr[u].s[2]].sz) u=tr[u].s[2];
            else k-=tr[tr[u].s[2]].sz,u=tr[u].s[1];
        }
    }
    return tr[u].r;
}
int rk(int &u,int k){
    int x=0,y=0;
    split(u,x,y,k-1);
    int res=tr[x].sz+1;
    u=merge(x,y);
    return res;
}
void ins(int &u,int v){
    int x=0,y=0,z=0;
    split(u,y,z,v);
    split(y,x,y,v-1);
    if(y==0){
        y=clone();
        tr[y].sz=1;
        tr[y].r=v;
    }else{
        tr[y].sz++;
    }
    u=merge(x,merge(y,z));
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int n,m,lst=0,rt=0;
    int ans=0;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        int v;
        cin>>v;
        ins(rt,v);
    }
    while(m--){
        int opt,v;
        cin>>opt>>v;
        v^=lst;
        if(opt==1){
            ins(rt,v);
        }else if(opt==2){
            int x=0,y=0,z=0;
            split(rt,y,z,v);
            split(y,x,y,v-1);
            tr[y].sz--;
            if(tr[y].sz==0) y=0;
            rt=merge(x,merge(y,z));
        }else if(opt==3){
            (lst=rk(rt,v)),ans^=lst;
        }else if(opt==4){
            (lst=kth(rt,v)),ans^=lst;
        }else if(opt==5){
            (lst=kth(rt,rk(rt,v)-1)),ans^=lst;
        }else (lst=kth(rt,rk(rt,v+1))),ans^=lst;
    }
    cout<<ans<<'\n';
    return 0;
}