无旋Treap教程

无旋Treap是一种非常精简的平衡树,定义也挺简单的,致力于替代splay等反人类旋转树

定义

$fix$:决定节点间父子关系的随机权重(就是作为堆的key)

$val$:真实的权重,决定节点间中序关系

$split(cur,pivot,u,v)$:把当前的$cur$树划分成$u,v$子树,按照$pivot$大小划分

$merge(u,v)$:把$u,v$子树合并,按照$fix$决定树的结构

细节

一般treap更适合用于区间操作(把$pivot$按照$size$来划分即可,而树形操作则用$val$来比较),因此这里没有$cnt$来维护重复的节点个数

构造过程

构造就是逐个插入过程了,假如我们实现了$split$和$merge$,每次都按照插入的键值$val$来$split(root)$来划分小于等于$val$和大于$val$的子树$a$和$b$,把$a$和单一的新建节点$t$进行$merge$后再与$b$进行$merge$即可

够简单粗暴吧

其他操作

删除也是split后直接弃置单个节点再merge即可

排名split后拿size比一下就有了

前驱后继还是split后按照根的左右子树遍历就有了

(实在太方便了,但别忘了要merge回去)

核心操作

从前面的结论得出,只要实现了$split$和$merge$,其实已经完成80%的工作了

$split(cur,pivot,u,v)$操作中:

如果$pivot \lt val[cur]$,那就说明$b$囊括了$cur$及其右子树$rc[cur]$,剩余的$a$和$lc[cur]$递归处理

另一种情况是相似的

$merge(u,v)$操作中:

采用小根堆的做法,假定$u$子树中最大的值都小于$v$子树中最小的值

如果$fix[u] \lt fix[v]$,$u$则作为$v$的父节点,否则相反,剩余的关系递归处理

完成版

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;

namespace util {
    template<typename T>
    inline void empb(vector<T> &v,const T &arg) {
        v.emplace_back(arg);
    }
    inline void fast_io() { 
        ios::sync_with_stdio(0); 
        cin.tie(0); 
        cout.tie(0); 
    }
    inline int random() {
        static unsigned int SEED = 19260817;
        SEED = SEED * 998244353 + 12345;
        return SEED / 1024;
    }
} 
using namespace util;
struct Treap {
    vector<int> lc,rc;
    vector<int> fix,val;
    vector<int> size;

    int root;

    Treap():root(0) {
        state(0);
        size[0] = 0;
    }

    int state(int v) {
        empb(lc,0);
        empb(rc,0);
        empb(fix,util::random());
        empb(val,v);
        empb(size,1);
        return lc.size()-1;
    } 

    inline void push_up(int cur) {
        size[cur] = 1 + size[lc[cur]] + size[rc[cur]];
    }

    void split(int cur,int pivot,int &u,int &v) {
        if(!cur) {
            u = v = 0;
            return;
        }
        if(pivot < val[cur]) {
            v = cur;
            split(lc[cur],pivot,u,lc[cur]);
        } else {
            u = cur;
            split(rc[cur],pivot,rc[cur],v);
        }
        push_up(cur);
    }

    int merge(int u,int v) {
        if(!u) return v;
        if(!v) return u;
        if(fix[u] < fix[v]) {
            rc[u] = merge(rc[u],v);
            push_up(u);
            return u;
        } else {
            lc[v] = merge(u,lc[v]);
            push_up(v);
            return v;
        }
    }

    void add(int k) {
        if(!root) {
            root = state(k);
            return;
        }
        int u,v;
        int t = state(k);
        split(root,k,u,v);
        root = merge(merge(u,t),v);
    }

    void remove(int k) {
        int u,v;
        split(root,k,u,v);
        int x,y;
        split(u,k-1,x,y);
        y = merge(lc[y],rc[y]); 
        u = merge(x,y);
        root = merge(u,v);
    }

    int rank(int k) {
        int u,v;
        split(root,k-1,u,v);
        int res = size[u]+1;
        root = merge(u,v);
        return res;
    }

    int kth_node(int cur,int kth) {
        while(cur) {
            if(kth <= size[lc[cur]]) {
                cur = lc[cur];
            } else if(kth == size[lc[cur]]+1) {
                return cur;
            } else {
                kth -= size[lc[cur]]+1;
                cur = rc[cur];
            }
        }
        return 0;
    }
    int pre(int k) {
        int u,v;
        split(root,k-1,u,v);
        int x = kth_node(u,size[u]);
        root = merge(u,v);
        return x;
    }
    int succ(int k) {
        int u,v;
        split(root,k,u,v);
        int x = kth_node(v,1);
        root = merge(u,v);
        return x;
    }
};

int main() {
    fast_io();
    Treap treap;
    int n; cin >> n;
    for(int i = 0; i < n; i++) {
        int op,val;
        cin >> op >> val;
        switch(op) {
            case 1: treap.add(val); break;
            case 2: treap.remove(val); break;
            case 3: cout << treap.rank(val) << endl; break;
            case 4: cout << treap.val[treap.kth_node(treap.root,val)] << endl; break;
            case 5: 
                treap.add(val);
                cout << treap.val[treap.pre(val)] << endl;
                treap.remove(val); 
                break;
            case 6:
                treap.add(val);
                cout << treap.val[treap.succ(val)] << endl;
                treap.remove(val); 
                break;
            default:
                break;
        }
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注