Skip to content

Latest commit

 

History

History
188 lines (143 loc) · 18.2 KB

link_cut.md

File metadata and controls

188 lines (143 loc) · 18.2 KB
Raw

Splay-дерево

Splay-дерево (дерево Тарьяна-Слейтора) - двоичное дерево поиска, созданное Робертом Тарьяном и Даниелем Слейтером специально для ускорения работы другой структуры данных, которую мы рассмотрим позже. Splay-дерево позволяет быстро получать доступ к недавно использованным данным (вершинам) засчёт их "поднятия" к корню и имеет амортизированное время работы $\hat{O}(n,log,n)$.

Свойства

Основная операция в splay-дереве - это операция $expose(v)$, выполняющая балансировку дерева. Она при помощи серии операций $rotate$ делает вершину $v$ корнем дерева. Поворот вокруг ребра $(v, u)$ (где $u$ - предок $v$; будем обозначать эту операцию за $rotate(v)$) "поднимает" $v$ на уровень вверх, при этом "опуская" $u$ и не нарушая свойств двоичного дерева поиска. По сути, splay-дерево - это детерминированное декартово дерево с амортизированным временем работы (из-за чего нельзя эффективно сделать splay-дерево персистентным). Базовая функция для работы splay-дерева - $find(x)$ - находит вершину $u$ с максимальным ключом, не большим $x$. Реализуется $find(x)$ так же, как и в других деревьях поиска - обычным спуском, но после обязательно нужно выполнить $expose(u)$. Через $find(x)$ реализуются операции $split$ и $merge$:

  • $split(x, k)$ - так же, как и в декартовом дереве, принимает исходное дерево $x$ и возвращает два дерева $l$ и $r$, причём все ключи в $l$ меньше $k$, а все ключи в $r$ - не меньше $k$. Выполним операцию $find(k)$ в дереве $x$, после которой найденная вершина $u$ окажется корнем $x$; заметим, что тогда ключи всех вершин в поддереве левого сына $u$ (обозначим его за $l$) будут меньше $k$, то есть мы можем "отрезать" левое поддерево от $u$ и вернуть пару ${l, u}$.
  • $merge(l, r)$ - принимает два дерева $l$ и $r$ (причём все ключи в $l$ меньше всех ключей в $r$) и возвращает новое дерево $x$, состоящее из всех вершин $l$ и $r$. При помощи операции $find$ найдём в $r$ вершину с минимальным ключом, после чего она станет корнем $r$; заметим, что у неё не будет левого сына, тогда мы просто сделаем этим левым сыном всё дерево $l$. Остальные операции реализуются через эти три (например, $add(x)$, $remove(x)$ и т.д).

Реализация $expose(v)$

Если реализовать $expose(v)$ простой серией поворотов $rotate(v)$ (пока $v$ не станет корнем), то можно подобрать пример, когда она всегда будет отрабатывать за $O(n)$ (например, если дерево - это один путь, подвешенный за конец, и $find$ каждый раз затрагивает другой конец пути). Для достижения асимптотики $\hat{O}(n,log,n)$ при реализации $expose(v)$ используются три вспомогательные операции - zig, zig-zig и zig-zag - которые являются комбинациями операций $rotate$.

$zig-zig(v)$

Обозначим за $p(x)$ предка вершины $x$, а за $L(x)$ - функцию, возвращающую 0, если $x$ - левый сын $p(x)$ или $p(x)$ не существует, и 1, если $x$ - правый сын $p(x)$. Операция $zig-zig(v)$ применяется в том случае, если $v$ не является непосредственным сыном корня, и $L(x)=L(p(x))$. $zig-zig(v)$ состоит из двух операций - $rotate(v)$ и $rotate(w)$ (где $w$ - предок $v$ до выполнения $zig-zig(v)$) - которые выполняются именно в таком порядке.

$zig-zag(v)$

Операция $zig-zag(v)$ применяется в том случае, если $v$ не является непосредственным сыном корня, и $L(x)\neq L(p(x))$. $zig-zig(v)$ состоит из двух операций - $rotate(w)$ и $rotate(v)$ (где $w$ - предок $v$ до выполнения $zig-zag(v)$) - которые выполняются именно в таком порядке.

$zig(v)$

Операция $zig(v)$ применяется в том случае, если $v$ является непосредственным сыном корня, и представляет собой одну операцию $rotate(v)$.

Итоговый алгоритм

Таким образом, для реализации $expose(v)$ мы просто в цикле до тех пор, пока $v$ не станет корнем, рассматриваем три случая:

  1. $v$ - непосредственный сын корня. Тогда выполняем $zig(v)$.
  2. $L(v) = L(p(v))$ - тогда выполняем $zig-zig(v)$.
  3. $L(v) \neq L(p(v)$ - тогда выполняем $zig-zag(v)$.

Неявное splay-дерево

Давайте считать, что splay-дерево хранит некоторый массив, причём все элементы массива, за которые отвечают вершины в левом поддереве $x$, находятся левее элемента $x$, а все элементы в правом поддереве - правее $x$ - как в декартовом дереве по неявному ключу. Тогда $find(k)$ будет искать в дереве вершину, отвечающую за $k$-й слева элемент этого массива. Таким образом, неявное splay-дерево решает те же задачи, что и неявное декартово дерево. На практике splay-дерево обычно оказывается в несколько раз быстрее, чем декартово дерево, из-за малой константы (см. время работы), поэтому если не получается упихать декартово дерево, есть много времени и опыт написания splay-дерева, то можно попытаться использовать его (однако, опять же, персистентность прикрутить не получится).

Реализация

struct node {
    int x, sz = 1;
    int p = -1, l = -1, r = -1;
    bool lft = 0;

    node() {}

    node(int x) : x(x) {}
};

node v[maxn];
int root = -1, mx = 0;

int gsz(int x) {
    return (x == -1 ? 0 : v[x].sz);
}

void upd(int x) {
    v[x].sz = 1 + gsz(v[x].l) + gsz(v[x].r);
}

// Отсоединяет вершину от предка, обновляя необходимые параметры

void disconnect(int x) {
    if (x == -1 || v[x].p == -1) return;
    if (v[v[x].p].l == x) v[v[x].p].l = -1;
    else v[v[x].p].r = -1;
    upd(v[x].p); v[x].p = -1; v[x].lft = 0;
}

// Делает вершину x левым или правым (в зависимости от lft) сыном y

void connect(int x, int y, bool lft) {
    if (x == -1 || y == -1) return;
    v[x].lft = lft; v[x].p = y;
    if (lft) v[y].l = x;
    else v[y].r = x;
    upd(y);
}

void rotate(int x) {
    int y = v[x].p, z = v[y].p, yl = v[y].lft, xl = v[x].lft;
    disconnect(x); disconnect(y);
    if (xl) {
        int b = v[x].r;
        disconnect(b); connect(b, y, 1); connect(y, x, 0);
    } else {
        int b = v[x].l;
        disconnect(b); connect(b, y, 0); connect(y, x, 1);
    }
    connect(x, z, yl);
}

// Если вместо expose написать splay, то больше людей поймут, что вы написали splay-дерево, посмотрев код посылки на кф 

void splay(int x) {
    if (x == -1) return;
    while (v[x].p != -1) {
        int y = v[x].p;
        if (v[y].p == -1) {
            rotate(x);
            break;
        }
        if (v[x].lft == v[y].lft) {
            rotate(y);
            rotate(x);
        } else {
            rotate(x);
            rotate(x);
        }
    }
    root = x;
}

// Функция find, которую я зачем-то назвал get

int get(int x, int k) {
    if (x == -1) return -1;
    while (1) {
        if (gsz(v[x].l) == k)
            break;
        if (k < gsz(v[x].l)) {
            x = v[x].l;
        } else {
            k -= (gsz(v[x].l) + 1);
            x = v[x].r;
        }
    }
    splay(x);
    return x;
}

pair<int, int> split(int x, int k) {
    if (x == -1) return {-1, -1};
    if (k == 0) return {-1, x};
    int aut = get(x, k - 1);
    int gg = v[aut].r;
    disconnect(gg);
    return {aut, gg};
}

int merge(int l, int r) {
    if (l == -1) return r;
    if (r == -1) return l;
    int bs = gsz(l);
    int aut = get(l, bs - 1);
    connect(r, aut, 0);
    return aut;
}

Это первая и последняя реализация splay-дерева, которую я писал, поэтому код такой длинный. Самое болезненное - дебагать обновление параметров вершин при переподвешивании.

Время работы

Сперва введём необходимые обозначения: $t_i$ - это время работы splay-дерева на $i$-м запросе, $T$ - это суммарное время работы дерева на всех запросах. Доказательство времени работы будем проводить при помощи метода потенциалов. Заключается он в следующем: пусть есть структура данных размера $n$, и мы хотим оценить амортизированное время её работы на $q$ запросах. Для каждого из $q+1$ состояний структуры введём величину $\Phi_{i}$ - потенциал. Также введём величину $a_i=t_i+\Phi_{i}-\Phi_{i-1}$ - стоимость $i$-й операции. Утверждается, что если $a_i=O(f(n,q))$ для некоторой функции $f$ и $\Phi_{i}=O(n\cdot f(n,q))$, то $T=O(f(n,q))$. Доказательство этого факта довольно простое, мы не будем его приводить, и перейдём непосредственно к доказательству времени работы splay-дерева. Обозначим за $C(v)$ размер поддерева вершины $v$. Тогда потенциалом $\Phi$ нашего дерева назовём сумму двоичных логарифомв $C(v)$ по всем вершинам $v$ дерева (для краткости обозначим $r(v)=log_2,C(v)$). Заметим, что эта величина неотрицательная и не больше $O(n,log,n)$. ааааааа что за жесть интересно зачем я вообще это пишу если есть викиконспекты (видимо потому что прилагать чистый код было бы тупо)

Link-cut tree

Рассмотрим следующую задачу:

Дан лес из $n$ вершин. Приходят запросы трёх типов:

  • $link(u,,v)$ - соединить вершины $u$ и $v$ ребром
  • $cut(u,,v)$ - удалить ребро между вершинами $u$ и $v$
  • $get(u,,v)$ - найти длину пути между $u$ и $v$ Нужно ответить на все запросы третьего типа. Гарантируется, что после каждого запроса граф остаётся лесом.

Существует структура данных, которая решает эту задачу, с амортизированным временем работы $O(n,log,n)$ - Link-Cut Tree, изобретённая Тарьяном и Слейтором (именно для достижения такой оценки и создавалось splay-дерево).

Основная идея

Подвесим каждое дерево нашего леса за некоторую вершину и ориентируем рёбра в сторону корня. Введём операцию $expose(x)$, которая делает вершину $x$ корнем своего дерева. Пусть старым корнем была вершина $y$, и мы применили операцию $expose(x)$. После этого нам нужно сменить ориентацию каждого ребра на пути между $x$ и $y$ на противоположную, чтобы ничего не сломалось. Рассмотрим, как мы тогда будем обрабатывать наши запросы:

  • $link(u, v)$ - в дереве вершины $u$ выполним операцию $expose(u)$, в дереве вершины $v$ - операцию $expose(v)$, и затем просто соединим $u$ с $v$ ребром, и вершина, в сторону которой будет ориентировано новое ребро, станет новым корнем дерева.
  • $cut(u, v)$ - просто удалим ребро между вершинами $u$ и $v$; вершина, в сторону которой было ориентировано ребро, останется в старом дереве, а другая вершина окажется в новом, её и следует назначить корнем нового дерева.
  • $get(u,,v)$ - выполним операцию $expose(u)$ и найдём глубину вершины $v$. Если реализовать операцию $expose$ напрямую, то каждый запрос в худшем случае будет обрабатыватся за $O(n)$; однако при помощи структур данных можно добиться амортизированного $O(n,log^2,n)$ или даже $O(n,log,n)$.

Ускорение работы

Мы описали в общих чертах алгоритм; теперь нужно понять, как выполнять эти операции быстро. Оказывается, что если мы разобьём каждое дерево на набор вершинно непересекающихся вертикальных путей и будем поддерживать эти пути при помощи декартовых деревьев по неявному ключу, то суммарная асимптотика алгоритма будет равна $O(n,log^2,n)$, что будет доказано в конце. Однако если вместо декартовых деревьев использовать splay-деревья, то асимптотика будет даже $O(n,log,n)$, и доказательство этого факта я не знаю. Разберём, как же работает быстрый алгоритм. Изначально мы строим декомпозицию каждого дерева на пути, причём не важно, какие именно, поэтому можно просто сделать $N$ путей длины 1. Пути мы храним в виде множества splay-деревьев, и для каждого пути мы храним указатель на предка самой высокой вершины. Когда нам нужно выполнить операцию $expose(x)$, мы "прыгаем" вверх по путям, попутно сливая их в один (то есть из вершины $x$ мы перемещаемся в верхнюю вершину пути, в котором лежит $x$; затем мы перемещаемся на одну вершину вверх и новый путь со старым (причём может оказаться так, что мы попали не на конец пути, а на середину, и тогда придётся "обрезать" путь в этом месте), затем прыгаем вверх по этому пути и т.д.). Затем просто выполняем разворот сегмента полученного объединённого пути, отвечающего за путь $(x; y)$. Казалось бы - совсем не ясно, почему этот алгоритм работает быстрее предыдущего. Однако выясняется очень любопытный факт: какие бы запросы не приходили, структура как бы сама оптимизирует себя, и итоговая асимптотика в любом случае оказывается $O(n,log^{(2)},n)$.

TODO