碎碎念

今天下午离线听了$WYX$大佬声情并茂的树套树讲解。

捞的一批的我决定先复习一下平衡树$QAQ$。

因为太菜了所以只会写$FHQ\ Treap$ 。

FHQ Treap

一种不带旋转的$Treap$。

通过对当前树的不断分裂与合并实现$Treap$的各种操作。

变量定义
int num;//树中节点数量 
int val[maxn];//节点权值 
int rnd[maxn];//Treap随机值 
int ls[maxn];//左儿子编号 
int rs[maxn];//右儿子编号 
int size[maxn];//以当前点为根的树的节点数量 
int sign[maxn];//懒标记 
向上传递
void push_up(int x){
    size[x]=size[ls[x]]+size[rs[x]]+1;
    //左子树节点数+右子树节点数+自己 
} 

基本操作

分割操作

①按权值分割

gOk8X.png

//将以rt为根的树按w分割为两颗树 
//权值小于等于w,以x为根的树
//权值大于w,以y为根的树 
void split(int rt,int w,int &x,int &y){
    if(rt==0){x=y=0;return;}
    if(val[rt]<=w) x=rt,split(rc[rt],w,rc[rt],y);
    else y=rt,split(lc[rt],w,x,lc[rt]);
    push_up(rt);
}

②按位置分裂

//将以rt为根的树按位置k分割为两颗树 
//下标小于k,以x为根的树   注意这里与按权值分割的不同
//下标大于等于k,以y为根的树 
void split(int rt,int k,int &x,int &y){
    if(!rt){x=y=0;return;}
    //size[lc[rt]]+1 表示以rt为根的树中rt的下标
    //大于k 继续找左边
    //小于等于k 找右边 这时我们找的是右边下标第 k-(size[lc[rt]]+1) 小的位置
    if(size[lc[rt]]+1>k) y=rt,split(lc[rt],k,x,lc[rt]);
    else x=rt,split(rc[rt],k-size[lc[rt]]-1,rc[rt],y); 
    push_up(rt);
}
合并操作
//合并以x和y为根的两颗树。
//保证x中的节点权值小于y中节点权值 
int merge(int x,int y){
    if(!x||!y) return x+y;//妙处!妙处!
    //x子树可能是y子树的左儿子
    //也可能y子树是x的右儿子
    //用创建节点时的随机数选择以上两种情况的一种进行合并
    //避免Treap退化为一条链 
    if(rnd[x]<rnd[y]){//随便判断一下
        //将y合并为x的右儿子。
        //考虑先将x的右儿子与y合并(称为tr) 
        //新树中x的右儿子就是tr的根节点 
        rc[x]=merge(rc[x],y);
        push_up(x);
        return x;//返回根节点 
    }
    else{//同理 
        lc[y]=merge(x,lc[y]);
        push_up(y);
        return y;//返回根节点 
    }
}
插入操作
int newp(int w){//新建一个节点 
    tail++; 
    val[tail]=w;rnd[tail]=rand();size[tail]=1;
    return tail;
}
void upd_ins(int w){//在树中插入一个权值为w的节点 
    num++;
    int x,y;
    //在树中插入节点
    //考虑先把rt按w分割为两棵树
    //左子树中的点一定小于等于w,右子树中的点一定大于w
    //最后 依次合并左子树,待插入的点,右子树 
    split(rt,w,x,y);
    rt=merge(merge(x,newp(w)),y);
}
删除操作
void upd_del(int w){//删除树中的一个节点 
    num--;
    int x,y,z;
    //在树中删除节点
    //考虑先把rt按w分割为y,z两棵树
    //再把权值小于等于w的树y按w-1分割为两棵树
    //最后依次合并x,lc[y],rc[y],z(相当于把y删掉了) 
    split(rt,w,y,z);
    split(y,w-1,x,y);
    rt=merge(merge(merge(x,lc[y]),rc[y]),z);
}
查询第k小数
int ask_kth(int x,int k){//查询树中第k小的元素
    //如果左子树的节点数量小于等于待查点的排名。
    //证明待查点在左子树 
    if(k<=size[lc[x]]) return ask_kth(lc[x],k);、
    //若等于左子树节点数量+1
    //证明待查点就是当前根 
    if(k==size[lc[x]]+1) return x;
    //若大于 证明在右子树中 
    return ask(rc[x],k-size[lc[x]]-1);
}
查询前驱 后继
ask_nex(int w){//查询某个值的后继 
    int x,y;
    //查询某个点的后继
    //考虑先把rt按w分为两棵树
    //那么w的后继一定是右子树中第一大的节点(等于w的被分在左边)
    //注意在查询结束后要合并分离的左右子树 
    split(rt,w,x,y);
    int res=val[ask_kth(y,1)];
    rt=merge(x,y);
    return res;
}
ask_pre(int w){//查询某个值前驱同理 
    int x,y;
    split(rt,w-1,x,y);
    int res=val[ask_kth(x,size[x])];
    rt=merge(x,y);
    return res;
} 

扩展操作

区间翻转

int sign_re[maxn];





区间修改

int sign_add[maxn];




启发式合并

合并两颗随机的平衡树。

因为$merge$操作中我们要求$x$中的结点小于等于$y$中的结点。

所以在不确定大小关系时不能随便合并。

在这样的情况下,

我们可以将$size$较小的树中每个结点拆下来分别插入另一颗树中。

//from来自size较小的那棵树,在函数外判断
void dsu_merge(int from,int &rt){
    if(!from) return;
    int x,y;
    split(rt,val[from],x,y);
    rt=merge(merge(x,newp(val[from])),y);
    dsu_merge(lc[from],rt);
    dsu_merge(rc[from],rt);
} 

撒花★,°:.☆( ̄▽ ̄)/$:.°★

撒cuancuan还没写完