平衡树笔记——fhq Treap

Augury · 2023-02-08 20:10:21 · 个人记录

平衡树笔记——\text{fhq Treap}

普通的二叉搜索树

定义

• 空树是一棵二叉搜索树。
• 对于每一个点，如果它的左子树不为空，那么左子树上的所有点的权值要小于这个点的权值。
• 对于每一个点，如果它的右子树不为空，那么阿巴阿巴……
• 二叉搜索树的左右子树都是二叉搜索树。

直接 \text{fhq Treap}

为啥不先写一下普通二叉平衡树或者 \text{AVL} ？

去问了机房的几位大佬，也在洛谷发了篇帖子，都说这俩没啥用，推荐直接跳过这俩，先 \text{fhq} 或者 \text{Splay} 。

随机打乱爆杀一切毒瘤数据

进入正题……

基本操作： \text{split} 和 \text{merge} 。

我们需要 5 个基本信息：

1. 左右子树编号
2. 这个节点的值
3. 索引（随机分配）
4. 子树大小

没什么用的代码

struct node{
    int l,r,val,key,size;
}fhq[maxn];
int cnt;
int newnode(int val){
    fhq[++cnt].val=val;
    fhq[cnt].size=1;
    fhq[cnt].key=rand();
    return cnt;
}
void update(int now){//更新大小
    fhq[now].size=fhq[fhq[now].l].size+fhq[fhq[now].r].size+1;
}

分裂

按值分裂

• 给定一个 val ，把一棵树分裂成两棵树，其中一棵树全部 \le val ，另一棵全部 >val 给定的值。

按大小分裂（排名分裂）

• 阿巴阿巴……（同上），其中一棵树中所有元素的排名 \le val ，另一棵 >val 。

一般使用按值分裂。

void split(int now,int val,int &x,int &y){//权值分裂
    if(!now)x=y=0;
    else{
        if(fhq[now].val<=val){
            x=now;
            split(fhq[now].r,val,fhq[now].r,y);//递归右儿子，看有没有可以放在左子树的节点
        }
        else{
            y=now;
            split(fhq[now].l,val,x,fhq[now].l);
        }
        update(now);
    }
}

void split(int now,int val,int &x,int &y){//排名分裂
    if(!now)x=y=0;
    else{
        if(val<=fhq[fhq[now].l].size){
            y=now;
            split(fhq[now].l,val,x,fhq[now].r);
        }
        else{
            x=now;
            split(fhq[now].r,val-fhq[fhq[now].l].size-1,fhq[now].r,y);
        }
        update(now);
    }
}

合并

给 x 和 y 两棵树， x 树中的值全部小于 y 的，并且合并出的树依旧满足 \text{Treap} 的性质。

int merge(int x,int y){
    if(!x||!y)return x+y;
    if(fhq[x].key>fhq[y].key){
        fhq[x].r=merge(fhq[x].r,y);
        update(x);
        return x;
    }
    else{
        fhq[y].l=merge(x,fhq[y].l);
        update(y);
        return y;
    }
}

那这俩操作有啥用吗？

插入

我们设要插入的值为 val 。

1. 按 val 分裂成 x 和 y 。
2. 合并 x 和新节点和 y 。
3. 没了……

稍微具体一点？

把 x 和新节点合并一下，然后用把这棵合并出来的新树和 y 合并一下。

void ins(int val){
    int x,y;
    split(root,val,x,y);
    root=merge(merge(x,newnode(val)),y);
}

删除

稍微有一点点麻烦，需要四步 (\ddot{\smallsmile})

1. 按 val 把原树分成 x 和 z 两部分
2. 按 val-1 把 x 分裂成 x 和 y ，此时 y 上的所有节点一定等于 val 。
3. 于是，我们把 y 的根去掉，也就是令 y=\operatorname{merge}(l[y],r[y]) 。
4. 最后，合并 x 、 y 和 z 即可。

void del(int val){
    int x,y,z;
    split(root,val,x,z);
    split(x,val-1,x,y);
    y=merge(fhq[y].l,fhq[y].r);
    root=merge(merge(x,y),z);
}

查询排名

1. 按照 val-1 分成 x 和 y
2. 排名就是 sz[x]+1
3. 合并 x 和 y

int getrank(int val){
    int x,y,ans;
    split(root,val-1,x,y);
    ans=fhq[x].size+1;
    root=merge(x,y);
    return ans;
}

查询排名对应的数

这里是非递归写法

int getnum(int rank){
    int now=root;
    while(now){
        if(fhq[fhq[now].l].size+1==rank){
            break;
        }
        else if(fhq[fhq[now].l].size>=rank){
            now=fhq[now].l;
        }
        else{
            rank-=fhq[fhq[now].l].size+1;
            now=fhq[now].r;
        }
    }
    return fhq[now].val;
}

前驱/后继

• 前驱
  • 按照 val-1 分成 x 和 y ，则 x 里面最右的就是 val 的前驱
• 后继
  • 按照 val 分成 x 和 y ，则 y 里面最左的就是 val 的后继

int pre(int val){
    int x,y;
    split(root,val-1,x,y);
    int now=x;
    while(fhq[now].r)now=fhq[now].r;
    int ans=fhq[now].val;
    root=merge(x,y);
    return ans;
}
int nxt(int val){
    int x,y;
    split(root,val,x,y);
    int now=y;
    while(fhq[now].l)now=fhq[now].l;
    int ans=fhq[now].val;
    root=merge(x,y);
    return ans;
}

然后我们来看题……

例题 1

P3369 【模板】普通平衡树

题意

就是板子，没啥好说的

做法

直接放代码吧（也就是把上面那一堆连起来）

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int n;
struct node{
    int l,r,val,key,size;
}fhq[maxn];
int cnt,root;
int newnode(int val){
    fhq[++cnt].val=val;
    fhq[cnt].size=1;
    fhq[cnt].key=rand();
    return cnt;
}
void update(int now){
    fhq[now].size=fhq[fhq[now].l].size+fhq[fhq[now].r].size+1;
}
void split(int now,int val,int &x,int &y){
    if(!now)x=y=0;
    else{
        if(fhq[now].val<=val){
            x=now;
            split(fhq[now].r,val,fhq[now].r,y);
        }
        else{
            y=now;
            split(fhq[now].l,val,x,fhq[now].l);
        }
        update(now);
    }
}
int merge(int x,int y){
    if(!x||!y)return x+y;
    if(fhq[x].key>fhq[y].key){
        fhq[x].r=merge(fhq[x].r,y);
        update(x);
        return x;
    }
    else{
        fhq[y].l=merge(x,fhq[y].l);
        update(y);
        return y;
    }
}
void ins(int val){
    int x,y;
    split(root,val,x,y);
    root=merge(merge(x,newnode(val)),y);
}
void del(int val){
    int x,y,z;
    split(root,val,x,z);
    split(x,val-1,x,y);
    y=merge(fhq[y].l,fhq[y].r);
    root=merge(merge(x,y),z);
}
int getrank(int val){
    int x,y,ans;
    split(root,val-1,x,y);
    ans=fhq[x].size+1;
    root=merge(x,y);
    return ans;
}
int getnum(int rank){
    int now=root;
    while(now){
        if(fhq[fhq[now].l].size+1==rank){
            break;
        }
        else if(fhq[fhq[now].l].size>=rank){
            now=fhq[now].l;
        }
        else{
            rank-=fhq[fhq[now].l].size+1;
            now=fhq[now].r;
        }
    }
    return fhq[now].val;
}
int pre(int val){
    int x,y;
    split(root,val-1,x,y);
    int now=x;
    while(fhq[now].r)now=fhq[now].r;
    int ans=fhq[now].val;
    root=merge(x,y);
    return ans;
}
int nxt(int val){
    int x,y;
    split(root,val,x,y);
    int now=y;
    while(fhq[now].l)now=fhq[now].l;
    int ans=fhq[now].val;
    root=merge(x,y);
    return ans;
}
int main(){
    srand(time(0));
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        int opt,x;
        scanf("%d%d",&opt,&x);
        if(opt==1)ins(x);
        if(opt==2)del(x);
        if(opt==3)cout<<getrank(x)<<endl;
        if(opt==4)cout<<getnum(x)<<endl;
        if(opt==5)cout<<pre(x)<<endl;
        if(opt==6)cout<<nxt(x)<<endl;
    }
    return 0;
}

例题 2

P3850 [TJOI2007]书架

题意

• 给定一排书，要求支持两种操作
  1. 插入（初始 n 次 + 后续 m 次）
  2. 查询（q 次）
• n\le 200,m\le10^5,q\le10^4

做法

• 显然是要在 \log n 的时间内完成单次操作。
• 我们考虑用 \text{fhq Treap} 维护。
• 为啥呢？
• 因为分裂、合并不会影响树内部元素的相对位置，所以我们可以直接用 \text{fhq Treap} 实现。
• 这里要用到我们一般不会用到的排名分裂。(???)
• 考虑插入操作：
  • 设我们要插入到 val 位置
  • 我们按照 val 排名分裂成 x 和 y 两棵树
  • 合并 x 和 \operatorname{newnode} 到 x ，再合并 x 和 y 即可
• 考虑查询：
  • 设要查询位置为 val 的值
  • 按照 val 把原树分裂成 x 和 y
  • 按照 1 把 y 分裂成 y 和 z ，这样 y 自己就出来啦
  • 要求的值就是 y 储存的值啦
  • 最后合并 x 和 y 和 z 到 root 即可。

\textit{Talk is cheap. Show me the code.}

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
struct node{
    int l,r,key,size;
    string s;
}fhq[maxn];
int cnt,root;
int n,m,q;
int newnode(string s){
    fhq[++cnt].size=1;
    fhq[cnt].key=rand();
    fhq[cnt].s=s;
    return cnt;
}
void update(int now){
    fhq[now].size=fhq[fhq[now].l].size+fhq[fhq[now].r].size+1;
}
void split(int now,int val,int &x,int &y){//排名分裂
    if(!now)x=y=0;
    else{
        if(val<=fhq[fhq[now].l].size){
            y=now;
            split(fhq[now].l,val,x,fhq[now].l);
        }
        else{
            x=now;
            split(fhq[now].r,val-fhq[fhq[now].l].size-1,fhq[now].r,y);
        }
        update(now);
    }
}
int merge(int x,int y){
    if(!x||!y)return x+y;
    if(fhq[x].key>fhq[y].key){
        fhq[x].r=merge(fhq[x].r,y);
        update(x);
        return x;
    }
    else{
        fhq[y].l=merge(x,fhq[y].l);
        update(y);
        return y;
    }
}
void ins(int val,string s){
    int x,y;
    split(root,val,x,y);
    root=merge(merge(x,newnode(s)),y);
}
string get(int val){
    int x,y,z;
    split(root,val,x,y);
    split(y,1,y,z);
    string ans=fhq[y].s;
    merge(merge(x,y),z);
    return ans;
}
int main(){
    srand(time(0));
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        string tmp;
        cin>>tmp;
        ins(i-1,tmp);
    }
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        string tmp;
        int pos;
        cin>>tmp>>pos;
        ins(pos,tmp);
    }
    scanf("%d",&q);
    for(int i=1;i<=q;i++){
        int tmp;
        scanf("%d",&tmp);
        cout<<get(tmp)<<endl;
    }
    return 0;
}

例题 3

P3224 [HNOI2012]永无乡

题意

• 两种操作
  • 加入一条边
  • 查询与 y 联通的点中 p_i 第 k 小的点的编号

做法

• 我们考虑 \text{fhq Treap} 的合并。
• 如果采取启发式合并，那么阿巴阿巴……，每个点最多被合并 \log n 次。
• 那么怎么完成单次合并呢捏？
• 对于每次加边，先判断这两个点是否在同一连通块中，如果是，直接跳过。
• 如果不是，那么考虑合并这两棵树。
• 我们设这两棵树编号为 x 和 y 。
  • 遍历 x 中的所有节点，然后把 x 中的点一个一个 \operatorname{insert} 到 y 里面即可。
• 注意事项：
  • 只要开一个树的数组即可
  • 加点、预处理时与正常的操作不同

\textit{Talk is cheap. Show me the code.}

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int n,m,q;
int p[maxn];
int mp[maxn];
int fa[maxn];
struct node{
    int l,r,val,key,size;
};
node fhq[maxn];
int root,cnt;
int find(int now){//查询并查集
    if(fa[now]==now)return now;
    return fa[now]=find(fa[now]);
}
void update(int now){
    fhq[now].size=fhq[fhq[now].l].size+fhq[fhq[now].r].size+1;
}
void split(int now,int val,int &x,int &y){//普普通通的分裂
    if(!now)x=y=0;
    else{
        if(fhq[now].val<=val){
            x=now;
            split(fhq[now].r,val,fhq[now].r,y);
        }
        else{
            y=now;
            split(fhq[now].l,val,x,fhq[now].l);
        }
        update(now);
    }
}
int merge(int x,int y){//普普通通的合并
    if(!x||!y)return x+y;
    if(fhq[x].key>fhq[y].key){
        fhq[x].r=merge(fhq[x].r,y);
        update(x);
        return x;
    }
    else{
        fhq[y].l=merge(x,fhq[y].l);
        update(y);
        return y;
    }
}
void ins(int &pos,int now){//在pos位置插入now
    int x,y;
    int val=p[now];
    split(pos,val,x,y);
    pos=merge(merge(x,now),y);
}
int get(int pos,int rank){//查询
    int now=pos;
    while(now){
        if(fhq[fhq[now].l].size+1==rank){
            break;
        }
        else if(fhq[fhq[now].l].size+1>=rank){
            now=fhq[now].l;
        }
        else{
            rank-=fhq[fhq[now].l].size+1;
            now=fhq[now].r;
        }
    }
    if(now)return mp[fhq[now].val];
    return -1;
}
int size(int pos){//查询大小
    return fhq[find(pos)].size;
}
void dfs(int x,int &y){//遍历x，加入y
    if(!x)return;
    dfs(fhq[x].l,y);
    dfs(fhq[x].r,y);
    fhq[x].l=fhq[x].r=0;
    ins(y,x);
}
int MERGE(int x,int y){//合并两棵树
    if(size(x)>size(y))swap(x,y);
    dfs(x,y);
    return y;
}
void print(int now){//输出，调试用
    if(!now)return;
    print(fhq[now].l);
    cout<<fhq[now].val<<' ';
    print(fhq[now].r);
}
int main(){
    srand(time(0));
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&p[i]);
    for(int i=1;i<=n;i++){//树的初始化
        fa[i]=i;
        fhq[i].size=1;
        fhq[i].l=fhq[i].r=0;
        fhq[i].key=rand();
        fhq[i].val=p[i];
    }
    for(int i=1;i<=n;i++)mp[p[i]]=i;
    for(int i=1;i<=m;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        if(find(u)==find(v))continue;
        int tmp=MERGE(find(u),find(v));
        fa[find(u)]=fa[find(v)]=fa[tmp]=tmp;
    }
    scanf("%d",&q);
    for(int i=1;i<=q;i++){
        char opt;
        int x,y;
        cin>>opt;
        scanf("%d%d",&x,&y);
        if(opt=='B'){
            if(find(x)==find(y))continue;
            int tmp=MERGE(find(x),find(y));
            fa[find(x)]=fa[find(y)]=fa[tmp]=tmp;
        }
        else{
            printf("%d\n",get(find(x),y));
        }
    }
    return 0;
}