Главная Курсы Ресурсы Задачи Национальная олимпиада Соревнования Таблица лидеров

...

Главная/Resources/Data Structures/Декартово дерево

Декартово дерево

Введение

Декартово дерево — это структура данных, которая сочетает бинарное дерево поиска и бинарную кучу. Название происходит от tree + heap.

Точнее, декартово дерево хранит пары $(X, Y)$ так, что:

это бинарное дерево поиска по $X$ ;
это куча по $Y$ .

Так что если узел содержит $(X_0, Y_0)$ , то:

Декартово дерево - Resources

Y0

)

все узлы в левом поддереве имеют ключи $X < X_0$ ;
все узлы в правом поддереве имеют ключи $X > X_0$ ;
все узлы в обоих поддеревьях имеют приоритеты $Y \leq Y_0$ .

Декартовы деревья поддерживают следующие операции:

Insert $(X, Y)$ за $O(\log N)$
Добавить новый узел в дерево. На практике мы обычно передаём только $X$ и генерируем $Y$ случайно.
Search $(X)$ за $O(\log N)$
Найти узел с ключом $X$ . Это работает точно так же, как в обычном бинарном дереве поиска.
Erase $(X)$ за $O(\log N)$
Удалить узел с ключом $X$ .
Build $(X_1, X_2, \ldots, X_N)$ за $O(N)$ Построить декартово дерево из отсортированного списка ключей.

Неявные декартовы деревья

Неявное декартово дерево — это модификация обычного декартова дерева, где ключи не хранятся явно.

Вместо этого позиция узла в массиве определяется размерами поддеревьев. Из-за этого неявное декартово дерево можно рассматривать как динамический массив, который эффективно поддерживает многие операции в онлайн-режиме.

Для массива $A_1, A_2, \ldots, A_N$ неявное декартово дерево может поддерживать:

Insert $(i, X)$
Вставить новый элемент $X$ в позицию $i$ , где $0 \leq i \leq N$ .
Erase $(i)$
Удалить элемент в позиции $i$ .
Get $(l, r)$
Вычислить сумму, минимум, максимум или другую информацию на отрезке $[l, r]$ .
Update $(l, r)$
Применить обновление на отрезке $[l, r]$ , например добавить значение или перекрасить сегмент.
Reverse $(l, r)$
Развернуть подмассив на отрезке $[l, r]$ .
Swap $(l_1, r_1, l_2, r_2)$ Поменять местами два подмассива.

Это делает неявные декартовы деревья очень мощными для задач на последовательности.

Реализация

Каждый узел хранит:

ключ x
приоритет y
указатель на левого ребёнка l
указатель на правого ребёнка r

Мы реализуем все основные операции декартова дерева, используя всего две вспомогательные операции:

Split
Merge

Split

Split(T, X) делит дерево T на два поддерева L и R так, что:

L содержит все ключи < X
R содержит все ключи >= X

Эта операция работает за $O(\log N)$ .

Идея

Предположим, что корень текущего дерева — v.

Если v->x < X, то v должен принадлежать левой части.
Мы рекурсивно делим правое поддерево.
Иначе v должен принадлежать правой части.
Мы рекурсивно делим левое поддерево.

Merge

Merge(T_1, T_2) объединяет два дерева T_1 и T_2 в одно дерево.

Эта операция предполагает, что все ключи в T_1 меньше всех ключей в T_2.

Она также работает за $O(\log N)$ .

Идея

Чтобы сохранить свойство кучи по приоритету:

если корень T_1 имеет больший приоритет, он становится корнем;
иначе корень T_2 становится корнем.

Затем мы рекурсивно объединяем оставшееся поддерево.

Неявные декартовы деревья

В неявном декартовом дереве ключ узла — это его позиция в массиве, но мы не храним это значение напрямую.

Вместо этого мы поддерживаем размер каждого поддерева.

Неявный ключ узла определяется:

количеством узлов в его левом поддереве;
плюс вкладом предков, когда узел лежит в правом поддереве.

Поскольку все операции спускаются вниз по дереву, мы можем вычислять позиции, используя размеры поддеревьев.

Поэтому мы добавляем ещё одно поле:

cnt — размер поддерева

Вспомогательные функции

Split и Merge для неявного декартова дерева

Теперь split(v, l, r, x) делит по позиции: левая часть получает первые x элементов.

O(N)

)

struct treap {
    treap *l, *r;
    int x, y;

    treap(int _x) : l(NULL), r(NULL), x(_x), y(rng()) {}
};

typedef treap* tree;

void split(tree v, tree &l, tree &r, int x) {
    if (v == NULL) {
        l = r = NULL;
        return;
    } else if (v->x < x) {
        split(v->r, v->r, r, x);
        l = v;
    } else {
        split(v->l, l, v->l, x);
        r = v;
    }
}

tree merge(tree l, tree r) {
    if (l == NULL) {
        return r;
    } else if (r == NULL) {
        return l;
    } else if (l->y > r->y) {
        l->r = merge(l->r, r);
        return l;
    } else {
        r->l = merge(l, r->l);
        return r;
    }
}

int get_cnt(tree v) {
    return (v ? v->cnt : 0);
}

void upd_cnt(tree v) {
    v->cnt = 1;
    v->cnt += (v->l ? v->l->cnt : 0);
    v->cnt += (v->r ? v->r->cnt : 0);
}

void split(tree v, tree &l, tree &r, int x) {
    if (v == NULL) {
        l = r = NULL;
        return;
    }
    if (get_cnt(v->l) < x) {
        split(v->r, v->r, r, x - get_cnt(v->l) - 1);
        l = v;
        upd_cnt(l);
    } else {
        split(v->l, l, v->l, x);
        r = v;
        upd_cnt(r);
    }
}

tree merge(tree l, tree r) {
    if (l == NULL) {
        return r;
    } else if (r == NULL) {
        return l;
    }
    if (l->y > r->y) {
        l->r = merge(l->r, r);
        upd_cnt(l);
        return l;
    } else {
        r->l = merge(l, r->l);
        upd_cnt(r);
        return r;
    }
}