kkogoro

平衡树模板
平衡树模板Treap普通平衡树#include <iostream> #include <cti...
扫描右侧二维码阅读全文
20
2018/11

平衡树模板

平衡树模板

Treap

普通平衡树

#include <iostream>
#include <ctime>
#include <cstdlib>
#include <cstdio>


inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}


struct Treap {
    static const int INF = 100000000;
    static const int MAXN = 100007;
    struct Node {
        int lc, rc, num, cnt, sum, dat;    
    } node[MAXN];
    int cntNode, root;
#define L(x) node[x].lc
#define R(x) node[x].rc
#define V(x) node[x].num
#define C(x) node[x].cnt
#define S(x) node[x].sum
#define D(x) node[x].dat
    inline int newNode(int val) {
        ++cntNode;
        V(cntNode) = val;
        D(cntNode) = std::rand();
        C(cntNode) = S(cntNode) = 1;
        return cntNode;
    }
    inline void pushUP(int cur) {
        S(cur) = S(L(cur)) + S(R(cur)) + C(cur);
        return;
    }
    inline void build() {
        root = newNode(-INF);
        newNode(INF);
        R(root) = 2;
        pushUP(root);
        return;
    }
    inline void zig(int &p) {
        int q = L(p);
        L(p) = R(q), R(q) = p, p = q;
        pushUP(R(p));
        pushUP(p);
        return;    
    }
    inline void zag(int &p) {
        int q = R(p);
        R(p) = L(q), L(q) = p, p = q;
        pushUP(L(p));
        pushUP(p);
        return;
    }
    void insert(int &p, int val) {
        if (!p) {
            p = newNode(val);
            return;    
        }
        if (val == V(p)) {
            ++C(p);
            pushUP(p);
            return;    
        }
        if (val < V(p)) {
            insert(L(p), val);
            if (D(L(p)) > D(p)) {
                zig(p);    
            }
        }
        else {
            insert(R(p), val);
            if (D(R(p)) > D(p)) {
                zag(p);    
            }
        }
        pushUP(p);
        return;
    }
    void erase(int &p, int val) {
        if (!p) {
            return;
        }
        
        if (val == V(p)) {
            if (C(p) > 1) {
                --C(p);
            }
            else if (L(p) || R(p)) {
                if (!R(p) || D(L(p)) > D(R(p))) {
                    zig(p);
                    erase(R(p), val);
                }
                else {
                    zag(p);
                    erase(L(p), val);
                }
            }
            else {
                p = 0;
            }
        }
        else {
            val < V(p) ? erase(L(p), val) : erase(R(p), val);    
        }
        pushUP(p);
        return;
    }
    int getRank(int &p, int val) {
        if (!p) {
            return 0;
        }
        if (val == V(p)) {
            return S(L(p)) + 1;    
        }
        if (val < V(p)) {
            return getRank(L(p), val);
        }
        return S(L(p)) + C(p) + getRank(R(p), val);
    }
    int getNum(int &p, int rank) {
        if (!p) {
            return INF;
        }
        if (S(L(p)) >= rank) {
            return getNum(L(p), rank);    
        }
        if (S(L(p)) + C(p) >= rank) {
            return V(p);
        }
        return getNum(R(p), rank - S(L(p)) - C(p));
    }
    int getPre(int val) {
        int ans = 0, p = root;
        while (p > 0) {
            if (val > V(p)) {
                ans = p;
                p = R(p);    
            }
            else {
                p = L(p);
            }
        }
        return V(ans);
    }
    int getNext(int val) {
        int ans = 0, p = root;
        while (p > 0) {
            if (val < V(p)) {
                ans = p;
                p = L(p);
            }
            else {
                p = R(p);
            }
        }
        return V(ans);
    }
#undef L
#undef R
#undef V
#undef C
#undef S
#undef D
} tree_1;


namespace BST {
    inline void init() {
        tree_1.build();
        return;
    }
    inline void insert(int val) {
        tree_1.insert(tree_1.root, val);
        return;
    }
    inline void erase(int val) {
        tree_1.erase(tree_1.root, val);
        return;
    }
    inline int getRank(int val) {
        return tree_1.getRank(tree_1.root, val) - 1;
    }
    inline int getNum(int rank) {
        return tree_1.getNum(tree_1.root, rank + 1);
    }
    inline int getPre(int val) {
        return tree_1.getPre(val);
    }
    inline int getNext(int val) {
        return tree_1.getNext(val);    
    }
}


int main() {
    srand(time(NULL));
    
    BST::init();
    int n = read();
    while (n--) {
        int opt = read();
        int x = read();
        switch(opt) {
            case 1 :
                BST::insert(x);
                break;
            case 2 :
                BST::erase(x);
                break;
            case 3 :
                printf("%d\n", BST::getRank(x));
                break;
            case 4 :
                printf("%d\n", BST::getNum(x));
                break;
            case 5 :
                printf("%d\n", BST::getPre(x));
                break;
            case 6 :
                printf("%d\n", BST::getNext(x));
                break;
        }
    }
    return 0;
}

非严格前驱

int getPre(int val) {
    int ans = 0, p = root;
    while (p > 0) {
        if (val > V(p)) {
            ans = p;
            p = R(p);    
        }
        else {
            if (val == V(p)) {
                ans = p;
                break; //break很重要!
            }
            p = L(p);
        }
    }
    return V(ans);
}

Splay

文艺平衡树

#include <iostream>
#include <cstdio>


inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10  + ch - '0';
        ch = getchar();
    }
    return x * f;
}


const int MAXN = 100007;

struct Splay {
    struct Node {
        int fa, ch[2], sum, tag;
    } node[MAXN];

#define F(x) node[x].fa
#define H(x, y) node[x].ch[y]
#define S(x) node[x].sum
#define L(x) node[x].ch[0]
#define R(x) node[x].ch[1]
#define root node[0].ch[1]
#define T(x) node[x].tag
    
    inline void pushUP(int x) {
        S(x) = S(L(x)) + S(R(x)) + 1;
        return;
    }
    inline void pushDOWN(int x) {
        if (x == 0) return;
        if (T(x)) {
            std::swap(L(x), R(x));
            T(L(x)) ^= 1;
            T(R(x)) ^= 1;
            T(x) = 0;
        }
        return;
    }
    inline int indent(int x) {
        return H(F(x), 0) == x ? 0 : 1;    
    }
    inline void connect(int x, int f, int how) {
        F(x) = f, H(f, how) = x;
        return;    
    }
    inline void rotate(int x) {
        int y = F(x), r = F(F(x));
        int yson = indent(x), rson = indent(y);
        connect(H(x, yson ^ 1), y, yson);
        connect(y, x, yson ^ 1);
        connect(x, r, rson);
        pushUP(y);
        pushUP(x);
        return;    
    }
    inline void splay(int x, int aim) {
        int Faim = F(aim);
        while (F(x) != Faim) {
            int y = F(x);
            if (y == aim) rotate(x);
            else if (indent(x) == indent(y)) rotate(y), rotate(x);
            else rotate(x), rotate(x);
        }
        return;
    }
    inline int getNum(int aim) {
        int p = root;
        while (1) {
            pushDOWN(p);
            if (S(L(p)) + 1 == aim) {
                return p;
            }
            else if (S(L(p)) >= aim) {
                p = L(p);    
            }
            else {
                aim -= S(L(p)) + 1;
                p = R(p);
            }
        }
    }    
    inline void rever(int l, int r) {
        int x = getNum(l);
        int y = getNum(r + 2);
        splay(x, root);
        splay(y, R(root));
        int z = L(y);
        T(z) ^= 1;
        return;
    }
    int build(int l, int r, int f) {
        if (l > r) return 0;
        int mid = (l + r) >> 1;
        F(mid) = f;
        L(mid) = build(l, mid - 1, mid);
        R(mid) = build(mid + 1, r, mid);
        pushUP(mid);
        return mid;    
    }
    void print(int p, int n) {
        pushDOWN(p);
        if (L(p)) print(L(p), n);
        if (p > 1 && p < n + 2) printf("%d ", p - 1);
        if (R(p)) print(R(p), n);
        return;    
    }
    
#undef F
#undef H
#undef S
#undef L
#undef R
#undef root
#undef T

} tree;

int main() {
    int n = read();
    int m = read();
    tree.build(1, n + 2, 0);
    tree.node[0].ch[1] = (1 + n + 2) >> 1;
    for (int i = 1; i <= m; ++i) {
        int l = read();
        int r = read();
        tree.rever(l, r);    
    }
    tree.print(tree.node[0].ch[1], n);
    return 0;
}

普通平衡树

#include <iostream>
#include <cstdio>



inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' ||ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}


struct Splay {
    static const int MAXN = 100007;
    static const int INF = 100000000;    

    struct Node {
        int fa, val, rec, sum, ch[2];    
    } node[MAXN];
    int cntNode;
#define F(x) node[x].fa
#define V(x) node[x].val
#define C(x) node[x].rec
#define S(x) node[x].sum
#define L(x) node[x].ch[0]
#define R(x) node[x].ch[1]
#define H(x, y) node[x].ch[y]
#define root node[0].ch[1]

    inline void pushUP(int x) {
        S(x) = S(L(x)) + S(R(x)) + C(x);
        return;
    }
    inline int newNode(int val, int f) {
        ++cntNode;
        V(cntNode) = val;
        C(cntNode) = S(cntNode) = 1;
        F(cntNode) = f;
        return cntNode;
    }
    inline void connect(int x, int f, int how) {
        H(f, how) = x, F(x) = f;
        return;
    }
    inline int indent(int x) {
        return L(F(x)) == x ? 0 : 1;
    }
    inline void rotate(int x) {
        int y = F(x), r = F(y);
        int yson = indent(x), rson = indent(y);
        connect(H(x, yson ^ 1), y, yson);
        connect(y, x, yson ^ 1);
        connect(x, r, rson);
        pushUP(y);
        pushUP(x);
        return;
    }
    inline void splay(int x, int aim) {
        int Faim = F(aim);
        while (F(x) != Faim) {
            int y = F(x);
            if (y == aim) rotate(x);
            else if (indent(x) == indent(y)) rotate(y), rotate(x);
            else rotate(x), rotate(x);    
        }
        return;
    }
    inline void insert(int val) {
        int p = root;
        if (root == 0) {
            root = newNode(val, 0);    
            return;
        }
        
        while (1) {
            ++S(p);
            if (V(p) == val) {
                ++C(p);
                splay(p, root);
                break;
            }
            
            int to = val < V(p) ? 0 : 1;
            if (H(p, to) == 0) {
                int born = newNode(val, p);
                H(p, to) = born;
                splay(born, root);
                break;    
            }
            p = H(p, to);
        }
        return;
    }
    
    inline int find(int val) {
        int p = root;
        while (1) {
            if (p == 0) return 0;
            if (V(p) == val) {
                splay(p, root);
                return p;
            }
            int to = val < V(p) ? 0 : 1;
            p = H(p, to);
        }
    }
    inline void erase(int val) {
        int p = find(val);
        if (p == 0) return;
        if (C(p) > 1) {
            --C(p);
            pushUP(p);
            return;
        }
        
        if (L(p) == 0 && R(p) == 0) {
            root = 0;
        }
        else if (L(p) == 0) {
            root = R(p);
            F(root) = 0;
        }
        else {
            int left = L(p);
            while (R(left)) left = R(left);
            splay(left, L(p));
            connect(R(root), left, 1);
            connect(left, 0, 1);
            pushUP(left);
        }
        return;
    }
    inline int getRank(int x) {
        return S(L(find(x))) + 1;
    }
    inline int getNum(int x) {
        int p = root;
        while (1) {
            if (S(L(p)) >= x) {
                p = L(p);
            }
            else if (S(L(p)) + C(p) >= x) {
                break;
            }
            else {
                x -= S(L(p)) + C(p);
                p = R(p);    
            }
        }
        splay(p, root);
        return V(p);
    }
    inline int lower(int x) {
        int p = root, ans = -INF;
        while (p) {
            if (V(p) < x) ans = std::max(ans, V(p));
            p = H(p, x <= V(p) ? 0 : 1);
        }
        return ans;
    }
    inline int upper(int x) {
        int p = root, ans = INF;
        while (p) {
            if (V(p) > x) ans = std::min(ans, V(p));
            p = H(p, x < V(p) ? 0 : 1);
        }
        return ans;
    }
#undef F
#undef V
#undef C
#undef S
#undef L
#undef R
#undef H
#undef root
} tree;


int main() {
    int n = read();
    while (n--) {
        int opt = read();
        int x = read();
        switch (opt) {
            case 1 :
                tree.insert(x);
                break;
            case 2 :
                tree.erase(x);
                break;
            case 3 :
                printf("%d\n", tree.getRank(x));
                break;
            case 4 :
                printf("%d\n", tree.getNum(x));
                break;
            case 5 :
                printf("%d\n", tree.lower(x));
                break;
            case 6 :
                printf("%d\n", tree.upper(x));
                break;
        }
    }
    return 0;
}

非严格前驱

inline int lower(int x) {
    int p = root, ans = -INF;
    while (p) {
        if (V(p) <= x) ans = std::max(ans, V(p));
        p = H(p, x <= V(p) ? 0 : 1);
    }
    return ans;
}
Last modification:November 21st, 2018 at 08:06 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment