Расширения декартова дерева
Перейти к навигации
Перейти к поиску
TLDR
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 : 2e9;
}
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 : 2e9;
}
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>;
Vector
|
getMinValue(lIndex, rIndex) class ImplicitTreap {
inline static minstd_rand gen;
struct Node {
int value, priority, size = 1, minValue;
Node *left = 0, *right = 0;
Node(int value) : value(value), priority(gen()), minValue(value) {}
} *root = 0;
int getSize(Node *n) {
return n ? n->size : 0;
}
int getMinValue(Node *n) {
return n ? n->minValue : 2e9;
}
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 k, Node *&a, Node *&b) {
if (!t) {
a = b = 0;
return;
}
if (getSize(t->left) < k) {
split(t->right, k - getSize(t->left) - 1, t->right, b);
a = t;
} else {
split(t->left, k, a, t->left);
b = t;
}
update(a);
update(b);
}
public:
void pushBack(int value) {
root = merge(root, new Node(value));
}
void pushFront(int value) {
root = merge(new Node(value), root);
}
void insertAfter(int index, int value) {
Node *a, *b;
split(root, index, a, b);
root = merge(a, merge(new Node(value), b));
}
void erase(int index) {
Node *a, *b, *c;
split(root, index, a, b);
split(b, 1, b, c);
root = merge(a, c);
}
void erase(int lIndex, int rIndex) {
Node *a, *b, *c;
split(root, lIndex, a, b);
split(b, rIndex - lIndex + 1, b, c);
root = merge(a, c);
}
int operator[](int index) {
Node *a, *b, *c;
split(root, index, a, b);
split(b, 1, b, c);
int res = b->value;
root = merge(a, merge(b, c));
return res;
}
void moveToFront(int lIndex, int rIndex) {
Node *a, *b, *c;
split(root, lIndex, a, b);
split(b, rIndex - lIndex + 1, b, c);
root = merge(b, merge(a, c));
}
void moveToBack(int lIndex, int rIndex) {
Node *a, *b, *c;
split(root, lIndex, a, b);
split(b, rIndex - lIndex + 1, b, c);
root = merge(a, merge(c, b));
}
int getMinValue(int lIndex, int rIndex) {
Node *a, *b, *c;
split(root, lIndex, a, b);
split(b, rIndex - lIndex + 1, b, c);
int res = getMinValue(b);
root = merge(a, merge(b, c));
return res;
}
};
|
reverse(lIndex, rIndex) class ImplicitTreap {
inline static minstd_rand gen;
struct Node {
int value, priority, size = 1, rev = 0;
Node *left = 0, *right = 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->left, n->right);
if (n->left)
n->left->rev ^= 1;
if (n->right)
n->right->rev ^= 1;
n->rev = 0;
}
}
void update(Node *n) {
if (n)
n->size = getSize(n->left) + 1 + getSize(n->right);
}
Node *merge(Node *a, Node *b) {
push(a);
push(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 k, Node *&a, Node *&b) {
push(t);
if (!t) {
a = b = 0;
return;
}
if (getSize(t->left) < k) {
split(t->right, k - getSize(t->left) - 1, t->right, b);
a = t;
} else {
split(t->left, k, a, t->left);
b = t;
}
update(a);
update(b);
}
public:
void pushBack(int value) {
root = merge(root, new Node(value));
}
void pushFront(int value) {
root = merge(new Node(value), root);
}
void insertAfter(int index, int value) {
Node *a, *b;
split(root, index, a, b);
root = merge(a, merge(new Node(value), b));
}
void erase(int index) {
Node *a, *b, *c;
split(root, index, a, b);
split(b, 1, b, c);
root = merge(a, c);
}
void erase(int lIndex, int rIndex) {
Node *a, *b, *c;
split(root, lIndex, a, b);
split(b, rIndex - lIndex + 1, b, c);
root = merge(a, c);
}
int operator[](int index) {
Node *a, *b, *c;
split(root, index, a, b);
split(b, 1, b, c);
int res = b->value;
root = merge(a, merge(b, c));
return res;
}
void moveToFront(int lIndex, int rIndex) {
Node *a, *b, *c;
split(root, lIndex, a, b);
split(b, rIndex - lIndex + 1, b, c);
root = merge(b, merge(a, c));
}
void moveToBack(int lIndex, int rIndex) {
Node *a, *b, *c;
split(root, lIndex, a, b);
split(b, rIndex - lIndex + 1, b, c);
root = merge(a, merge(c, b));
}
void reverse(int lIndex, int rIndex) {
Node *a, *b, *c;
split(root, lIndex, a, b);
split(b, rIndex - lIndex + 1, b, c);
b->rev = 1;
root = merge(a, merge(b, c));
}
};
|
Ссылки
Теория:
- Фолунин В. — Декартово дерево по неявному ключу
- 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
Задачи: