平衡树

这是一篇个人笔记，不希望大家学习。

Treap

Treap是一个非常非常好写只是略微看运气的平衡树写法。
先说一句，这篇随笔是写个 XF 看的啦，不是属于正式的算法介绍，因此你们看不看的懂我也不能保证啦

一、

平衡树基于二叉搜索树，而对于一颗二叉搜索树，上面的所有节点均满足：左儿子$<$节点$<$右儿子，因此任意一颗平衡树一样的也有这样的性质。

二、

为了降低时间复杂度，Treap总是先遍历优先度高的节点，确定优先度的方法就是在建立一个新节点时，对它随机一个新节点。
因此，在每一次删除或者加入操作时，我们也要维护它的这个性质，这就要使用 rotate 了。

三、Rotate：旋转函数

可以选择左旋或者右旋，每次都将改变右/左儿子与其父亲的深度关系。
根据代码模拟下不就好了嘛，放什么图啊

inline void rotate(ll &id,ll d){//direction
    ll tmp=ch[id][d^1];//这里解释一下：d^1可以使0变1，1变0
    ch[id][d^1]=ch[tmp][d];
    ch[tmp][d]=id;
    id=tmp;
    pushup(id);
    pushup(ch[id][d]);
}

四、

新建节点：

inline ll New(ll x){
    val[++tot]=x;
    dat[tot]=rand();
    size[tot]=cnt[tot]=1;
    return tot;   
}
inline void build(){
    root=New(-INF),ch[root][1]=New(INF);
    pushup(root);
}
inline void insert(ll &id,ll v){
    if(!id){
        id=New(v);
        return;
    }
    if(val[id]==v)  ++cnt[id];
    else{
        kk=v<val[id]?0:1;
        insert(ch[id][kk],v);
        if(dat[ch[id][kk]]>dat[id])
            rotate(id,kk^1);
    }
    pushup(id);
}

更新信息：

inline void pushup(ll x){
    size[x]=size[ch[x][1]]+size[ch[x][0]]+cnt[x];
}

删除节点：

inline void remove(ll &id,ll x){
    if(!id)             return;
    else{
        if(val[id]==x){
            if(cnt[id]>1){
                --cnt[id];
                pushup(id);
                return;
            }   
            else{
                if(ch[id][0]||ch[id][1]){
                    if(!ch[id][1]||dat[ch[id][0]]>dat[ch[id][1]])
                        rotate(id,1),remove(ch[id][1],x);
                    else   
                        rotate(id,0),remove(ch[id][0],x);
                    pushup(id);
                }
                else    id=0;
                return;
            }
        }
    }   
    kk=x<val[id]?0:1;
    remove(ch[id][kk],x);
    pushup(id);   
}

查分/查排名

inline ll getrank(ll id,ll x){
    if(!id)
        return -INF;
    if(val[id]==x)
        return size[ch[id][0]]+1;
    if(x<val[id])
        return getrank(ch[id][0],x);
    else    
        return getrank(ch[id][1],x)+size[ch[id][0]]+cnt[id];
}

inline ll getmark(ll id,ll x){
    if(!id)     return INF;
    if(x<=size[ch[id][0]])
        return getmark(ch[id][0],x);
    if(x<=size[ch[id][0]]+cnt[id])
        return val[id];
    return getmark(ch[id][1],x-size[ch[id][0]]-cnt[id]);
}   

查前驱

inline ll pre(ll x){
    ll id=root,prev;
    while(id){
        if(val[id]<x)
            prev=val[id],id=ch[id][1];
        else
            id=ch[id][0];
    }
    return prev;
}

这里如果当前节点的值比要寻找的值小的话，根据二叉搜索树的规则，应该选择往右边找，是否有更接近的值；如果大于的话，当然往左边找啦

后继把所有符号反过来就好啦。