Расширения декартова дерева
Перейти к навигации
Перейти к поиску
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;
}
};
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
Задачи: