fhq treap

首先是fhq treap的结构体和普通treap差不多

    struct node{
        int l,r,val,key,size;
    }

val是权值，我们根据权值确定左右儿子;
key是rand()下的随机值，我们根据这个随机值保证大根堆或小根堆

fhq treap可以解决大部分Splay的问题而且比Splay更短，效率差不多

1.分裂操作Split

    int split(int p,int v,int &x,int &y){
        if(!p){
            x=y=0;
            return;
        }
        if(tr[p].val<=v){
            x = p;
            split(tr[p].r,v,tr[p].r,y);
        }
        else y= p,split(tr[p].l,v,x,tr[p.l]);
        pushup(p); //做完之后更新信息（子树大小等）
    }

x表示分裂后的左子树的根节点，y表示分裂后的右子树的根节点。在分裂的过程中，我们比较当前点P的权值val和v的大小，如果val<=v,说明p以及p的左子树一定属于x,因为它们都比v要小，而P的右子树则不一定都比v小，需要递归给下一层做，此时可以令x = p,然后递归split(tr[p].r,v,tr[p].r,y);

2.合并操作merge

//我们假设建立的是小根堆
    void merge(int x,int y){//x是左树它的根节点的值一定比y小
        if(!x||!y) return x+y;//有一方是空的直接返回另一方
        if(tr[x].key<tr[y].key){//x的随机值小应该放在上面
            tr[x].r = merge(tr[x].r,y);
            pushup(x);
            return x;//返回根节点
        }
        else{
            tr[y].l = merge(x,tr[y].l);
            pushup(y);
            return y;
        } 
    }

3.插入操作Insert

首先是根据权值建立一个新的节点

    int new_node(int v){
        tr[++idx].val = v;
        tr[idx].size = 1;
        tr[idx].key = rand();
        return idx;
    }

    void insert(int v){ 
        int x,y,z;
        split(root,v,x,y);
        z = new_node(v);
        root = merge(merge(x,z),y);//先合并小的再合并大的
    }

4.删除一个数(del)

    void del(int v){
        int x,y,z;
        split(root,v,x,z);//权值为v的点按照split在x为根的子树中
        split(x,v-1,x,y);//现在权值为v的点是y,小于v的点在x中
        y = merge(tr[y].l,tr[y].r);//删掉tr[y]了
        root = merge(merge(x,y),z);
    }

5.找前驱Pre

找前驱就是找到一个小于v的最大数，可以把树按v-1分裂，这样x都是小于v的，设x的大小为size，只要找到以x为根的子树里的第size大的树就好了

    int get_k(int x,int k){
        int u = x;
        while(u){
            if(tr[tr[u].l].size<=k) u = tr[u].l;
            else if(tr[tr[u].l].size+1==k) return u;
            else k-=tr[tr[u].l].size+1,u = tr[u].r;
        }
    }

    int pre(int v){
        int x,y;
        split(root,v-1,x,y);
        int ans = get_k(x,tr[x].size);
        root = merge(x,y);//分裂完之后合并
        return ans;

    }

6.找后继next

同理只要改成按v分裂，找第一个数就行了。

    int next(int v){
        int x,y,ans;
        split(root,v-1,x,y);
        int ans = get_k(y,1);
        root = merge(x,y);
        return ans;
    }