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

Multimap с getMinValue

getMinValue(lKey, rKey) class Treap { inline static minstd_rand gen; struct Node { int key, priority, value, minValue; Node *left = 0, *right = 0; Node(int key, int value) : key(key), priority(gen()), value(value), minValue(value) {} } *root = 0; int getMinValue(Node *n) const { return n ? n->minValue : 1e9; } void update(Node *n) { if (n) n->minValue = min({ getMinValue(n->left), n->value, getMinValue(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); } public: void insert(int key, int value) { Node *a, *b; split(root, key, a, b); root = merge(a, merge(new Node(key, value), b)); } void erase(int key) { Node *a, *b, *c; split(root, key, a, b); split(b, key + 1, b, c); root = merge(a, c); } void eraseOne(int key) { Node *a, *b, *c; split(root, key, a, b); split(b, key + 1, b, c); if (b) b = merge(b->left, b->right); root = merge(a, merge(b, c)); } int getMinValue(int lKey, int rKey) { Node *a, *b, *c; split(root, lKey, a, b); split(b, rKey + 1, b, c); int res = getMinValue(b); root = merge(a, merge(b, c)); return res; } };

getMinValue(lIndex, rIndex) class Treap { inline static minstd_rand gen; struct Node { int key, priority, size = 1, value, minValue; Node *left = 0, *right = 0; Node(int key, int value) : key(key), priority(gen()), value(value), minValue(value) {} } *root = 0; int getSize(Node *n) const { return n ? n->size : 0; } int getMinValue(Node *n) const { return n ? n->minValue : 1e9; } void update(Node *n) { if (n) { n->size = getSize(n->left) + 1 + getSize(n->right); n->minValue = min({ getMinValue(n->left), n->value, getMinValue(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); } void splitByIndex(Node *t, int index, Node *&a, Node *&b) { if (!t) { a = b = 0; return; } int leftSize = getSize(t->left); if (leftSize < index) { splitByIndex(t->right, index - leftSize - 1, t->right, b); a = t; } else { splitByIndex(t->left, index, a, t->left); b = t; } update(a); update(b); } public: void insert(int key, int value) { Node *a, *b; split(root, key, a, b); root = merge(a, merge(new Node(key, value), b)); } void erase(int key) { Node *a, *b, *c; split(root, key, a, b); split(b, key + 1, b, c); root = merge(a, c); } void eraseOne(int key) { Node *a, *b, *c; split(root, key, a, b); split(b, key + 1, b, c); if (b) b = merge(b->left, b->right); root = merge(a, merge(b, c)); } int getMinValue(int lIndex, int rIndex) { Node *a, *b, *c; splitByIndex(root, lIndex, a, b); splitByIndex(b, rIndex - lIndex + 1, b, c); int res = getMinValue(b); root = merge(a, merge(b, c)); return res; } };

Multiset с indexOf(key), operator[], lessCount(key), greaterCount(key)

Одинаковые элементы хранятся в нескольких узлах class Treap { inline static minstd_rand gen; struct Node { int key, priority, size = 1; Node *left = 0, *right = 0; Node(int key) : key(key), priority(gen()) {} } *root = 0; int getSize(Node *n) const { return n ? n->size : 0; } void update(Node *n) { if (n) n->size = getSize(n->left) + 1 + getSize(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 (key < n->key) return indexOf(n->left, key); else if (n->key == key) return getSize(n->left); else return getSize(n->left) + 1 + indexOf(n->right, key); } int getByIndex(Node *n, int index) const { int leftSize = getSize(n->left); if (leftSize > index) return getByIndex(n->left, index); else if (leftSize == index) return n->key; else return getByIndex(n->right, index - leftSize - 1); } public: int size() const { return getSize(root); } int indexOf(int key) const { return indexOf(root, key); } int operator[](int index) const { return getByIndex(root, index); } void insert(int key) { Node *a, *b; split(root, key, a, b); root = merge(a, merge(new Node(key), b)); } void erase(int key) { Node *a, *b, *c; split(root, key, a, b); split(b, key + 1, b, c); root = merge(a, c); } void eraseOne(int key) { Node *a, *b, *c; split(root, key, a, b); split(b, key + 1, b, c); if (b) b = merge(b->left, b->right); root = merge(a, merge(b, c)); } int lessCount(int key) { Node *a, *b; split(root, key, a, b); int res = getSize(a); root = merge(a, b); return res; } int lessEqualCount(int key) { Node *a, *b; split(root, key + 1, a, b); int res = getSize(a); root = merge(a, b); return res; } int greaterCount(int key) { Node *a, *b; split(root, key + 1, a, b); int res = getSize(b); root = merge(a, b); return res; } int greaterEqualCount(int key) { Node *a, *b; split(root, key, a, b); int res = getSize(b); root = merge(a, b); return res; } };

Одинаковые элементы хранятся в одном узле class Treap { inline static minstd_rand gen; struct Node { int key, priority, nodeSize = 1, subtreeSize = 1; Node *left = 0, *right = 0; Node(int key) : key(key), priority(gen()) {} } *root = 0; 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 (key < n->key) return indexOf(n->left, key); else if (n->key == key) return getSubtreeSize(n->left); else return getSubtreeSize(n->left) + n->nodeSize + indexOf(n->right, 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 n->key; else return getByIndex(n->right, index - leftSize - n->nodeSize); } public: 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 *a, *b, *c; split(root, key, a, b); split(b, key + 1, b, c); if (b) { b->nodeSize++; b->subtreeSize++; } else { b = new Node(key); } root = merge(a, merge(b, c)); } void erase(int key) { Node *a, *b, *c; split(root, key, a, b); split(b, key + 1, b, c); root = merge(a, c); } void eraseOne(int key) { Node *a, *b, *c; split(root, key, a, b); split(b, key + 1, b, c); if (b) { b->nodeSize--; b->subtreeSize--; if (!b->nodeSize) b = 0; } root = merge(a, merge(b, c)); } int lessCount(int key) { Node *a, *b; split(root, key, a, b); int res = getSize(a); root = merge(a, b); return res; } int lessEqualCount(int key) { Node *a, *b; split(root, key + 1, a, b); int res = getSize(a); root = merge(a, b); return res; } int greaterCount(int key) { Node *a, *b; split(root, key + 1, a, b); int res = getSize(b); root = merge(a, b); return res; } int greaterEqualCount(int key) { Node *a, *b; split(root, key, a, b); int res = getSize(b); root = merge(a, b); return res; } };

Set с find_by_order(index) и order_of_key(key) через __gnu_pbds

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using ordered_set = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;

• Пример решения
• Codeforces — C++ STL: Policy based data structures

Прочее

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;
    }
};

minstd_rand gen;

class ITreap {
    struct Node {
        int value, priority, size = 1, rev = 0;
        Node *l = 0, *r = 0;
        Node(int value) : value(value), priority(gen()) {}
    } *root = 0;

    int getSize(Node *n) {
        return n ? n->size : 0;
    }

    void push(Node *n) {
        if (n && n->rev) {
            swap(n->l, n->r);
            if (n->l)
                n->l->rev ^= 1;
            if (n->r)
                n->r->rev ^= 1;
            n->rev = 0;
        }
    }

    void update(Node *n) {
        if (n)
            n->size = 1 + getSize(n->l) + getSize(n->r);
    }

    Node *merge(Node *a, Node *b) {
        push(a);
        push(b);
        if (!a || !b)
            return a ? a : b;
        if (a->priority > b->priority) {
            a->r = merge(a->r, b);
            update(a);
            return a;
        } else {
            b->l = merge(a, b->l);
            update(b);
            return b;
        }
    }

    void split(Node *t, int k, Node *&a, Node *&b) {
        push(t);
        if (!t) {
            a = b = 0;
            return;
        }
        if (getSize(t->l) < k) {
            split(t->r, k - getSize(t->l) - 1, t->r, b);
            a = t;
        } else {
            split(t->l, k, a, t->l);
            b = t;
        }
        update(a);
        update(b);
    }

public: 
    void pushBack(int value) {
        root = merge(root, new Node(value));
    }

    void reverse(int l, int r) {
        Node *a, *b, *c;
        split(root, l, a, b);
        split(b, r - l + 1, b, c);
        b->rev = 1;
        root = merge(a, merge(b, c));
    }

    int get(int i) {
        Node *a, *b, *c;
        split(root, i, a, b);
        split(b, 1, b, c);
        int res = b->value;
        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
• Задачи: Декартово дерево по неявному ключу
• Задачи: Дерево Корнеева