Расширения декартова дерева

pbds

minstd_rand gen;

class Treap {
    struct Node {
        int key, priority, nodeSize, subtreeSize;
        Node *left, *right;
        Node(int key) : key(key), priority(gen()), nodeSize(1), subtreeSize(1), left(0), right(0) {}
    } *root;
    int getSubtreeSize(Node *n) const {
        return n ? n->subtreeSize : 0;
    }
    void update(Node *n) {
        if (n) {
            n->subtreeSize = getSubtreeSize(n->left) + n->nodeSize + getSubtreeSize(n->right);
        }
    }
    Node *merge(Node *a, Node *b) {
        if (!a || !b) {
            return a ? a : b;
        }
        if (a->priority > b->priority) {
            a->right = merge(a->right, b);
            update(a);
            return a;
        } else {
            b->left = merge(a, b->left);
            update(b);
            return b;
        }
    }
    void split(Node *t, int key, Node *&a, Node *&b) {
        if (!t) {
            a = b = 0;
            return;
        }
        if (t->key < key) {
            split(t->right, key, t->right, b);
            a = t;
        } else {
            split(t->left, key, a, t->left);
            b = t;
        }
        update(a);
        update(b);
    }
    int indexOf(Node *n, int key) const {
        if (!n) {
            return 0;
        } else if (n->key < key) {
            return getSubtreeSize(n->left) + n->nodeSize + indexOf(n->right, key);
        } else if (n->key == key) {
            return getSubtreeSize(n->left);
        } else {
            return indexOf(n->left, key);
        }
    }
    int getByIndex(Node *n, int index) const {
        int leftSize = getSubtreeSize(n->left);
        if (leftSize > index) {
            return getByIndex(n->left, index);
        } else if (leftSize + n->nodeSize < index) {
            return getByIndex(n->right, index - leftSize - n->nodeSize);
        } else {
            return n->key;
        }
    }
public:
    Treap() : root(0) {}
    int size() const {
        return getSubtreeSize(root);
    }
    int indexOf(int key) const {
        return indexOf(root, key);
    }
    int operator [] (int index) const {
        return getByIndex(root, index);
    }
    void insert(int key) {
        Node *less, *equal, *greater;
        split(root, key, less, equal);
        split(equal, key + 1, equal, greater);
        if (equal) {
            equal->nodeSize++;
            equal->subtreeSize++;
        } else {
            equal = new Node(key);
        }
        equal = merge(equal, greater);
        root = merge(less, equal);
    }
    void erase(int key) {
        Node *less, *equal, *greater;
        split(root, key, less, equal);
        split(equal, key + 1, equal, greater);
        root = merge(less, greater);
    }
    void eraseOne(int key) {
        Node *less, *equal, *greater;
        split(root, key, less, equal);
        split(equal, key + 1, equal, greater);
        if (equal) {
            equal->nodeSize--;
            equal->subtreeSize--;
            if (!equal->nodeSize) {
                equal = 0;
            }
        }
        equal = merge(equal, greater);
        root = merge(less, equal);
    }
};

struct TN {
    int v, p, c, maxV;
    TN *l, *r;
    TN(int V) : v(V), p(rand()), c(1), maxV(V), l(0), r(0) {}
};
 
class ITreap {
    TN *root;
    int getMaxV(TN *n) {
        return n ? n->maxV : -(1 << 30);
    }
    int getC(TN *n) {
        return n ? n->c : 0;
    }
    void update(TN *n) {
        if (!n)
            return;
        n->c = 1 + getC(n->l) + getC(n->r);
        n->maxV = max(n->v, max(getMaxV(n->l), getMaxV(n->r)));
    }
    TN *merge(TN *a, TN *b) {
        if (!a || !b)
            return a ? a : b;
        if (a->p > b->p) {
            a->r = merge(a->r, b);
            update(a);
            return a;
        } else {
            b->l = merge(a, b->l);
            update(b);
            return b;
        }
    }
    void split(TN *t, int k, TN *&a, TN *&b) {
        if (!t) {
            a = b = 0;
            return;
        }
        if (getC(t->l) < k) {
            split(t->r, k - getC(t->l) - 1, t->r, b);
            a = t;             
        } else {
            split(t->l, k, a, t->l);
            b = t;   
        }
        update(a);
        update(b);
    }
public:
    ITreap() : root(0) {}
    int size() {
        return getC(root);
    }
    void insert(int pos, int v) {
        TN *a, *b;
        split(root, pos, a, b);
        root = merge(a, merge(new TN(v), b));
    }
    int getMax(int l, int r) {
        TN *a, *b, *c;
        split(root, l, a, b);
        split(b, r - l + 1, b, c);
        int res = getMaxV(b);
        root = merge(a, merge(b, c));
        return res;
    }
};

Ссылки

Теория:

• Фолунин В. — Декартово дерево по неявному ключу
• e-maxx.ru — Неявные декартовы деревья
• neerc.ifmo.ru/wiki — Декартово дерево по неявному ключу
• habrahabr.ru — Декартово дерево: Часть 3. Декартово дерево по неявному ключу
• Иващенко Д., Семенов К. Декартово дерево

Код:

• github.com/indy256/codelibrary/blob/master/cpp/structures/treap_indexed.cpp
• Algos — Cartesian tree using implicit keys

Задачи:

• informatics.mccme.ru — Курс «Структуры данных» — часть 4
• Задачи: Декартово дерево по неявному ключу
• Задачи: Дерево Корнеева