Расширения декартова дерева
Перейти к навигации
Перейти к поиску
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. Декартово дерево по неявному ключу
- Иващенко Д., Семенов К. Декартово дерево
Код:
- CodeLibrary — Treap with implicit key with interval modification
- Algos — Cartesian tree using implicit keys
Задачи: