Двоичные подъемы с линейной памятью
Часто в задачах на деревья используются двоичные подъемы. Они помогают искать LCA (наименьшего общего предка), какую-то функцию на пути и так далее. Однако они занимают $O(n \log n)$ памяти. В этой главе мы рассмотрим альтернативную структуру со схожей функциональностью, занимающую линейную память.
Идея
В двоичных подъемах мы для каждой вершины храним предков на $1$, $2$, $4$, $\ldots$, $2^k$ вверх. Чтобы сделать структуру линейной, мы будем хранить только двух предков: непосредственного отца (parent) и еще какого-то одного предка (jump). И тогда если мы для каждой вершины еще сохраним ее глубину (depth), то мы сможем легко отвечать на запросы. К примеру, если нам надо найти предка текущей вершины на какой-то глубине, то каждый раз, когда мы стоим в вершине, мы будем сначала смотреть на более длинный прыжок, если он не выше нужной нам вершины, будем совершать этот прыжок, а если же он все таки выше, то просто переходить в отца. Таким способом мы гарантировано придем в нужную вершину, осталось только построить такие прыжки, чтобы этот путь занимал всегда логарифмическое количество шагов.
При этом структура будет динамическая, так же как и обычные двоичные подъемы. То есть мы можем добавлять вершины в дерево по очереди, и старые прыжки не будут пересчитываться.
Остается лишь придумать, как построить прыжки. Давайте сделаем это следующим образом: если прыжок из нашего отца (par) имеет такую же длину, как и прыжок из прыжка нашего отца (jump[par]), то мы проведем ребро в прыжок прыжка нашего отца (jump[jump[par]]), а иначе проведем ребро просто в нашего отца. Если вы запутались, то рекомендую осознать код:
void add_leaf(int v, int par) {
parent[v] = par;
depth[v] = depth[par] + 1;
if (depth[par] - depth[jump[par]] == depth[jump[par]] - depth[jump[jump[par]]]) {
jump[v] = jump[jump[par]];
} else {
jump[v] = par;
}
}
Доказательство
Почему же с такими прыжками нам придется совершить лишь логарифмическое количество переходов? Для понимания полезно нарисовать картинку. Заметим, что на длину прыжка из вершины $v$ (а также длины прыжков из всех ее предков) влияет только ее глубина, но не структура дерева. Поэтому можно рассмотреть лишь ситуацию, в которой наше дерево является бамбуком. Давайте заметим, что длина любого прыжка равна степени двойки (если считать длину не по количеству ребер, а по количеству вершин). Действительно, для прыжка в отца длина равна $2$, а любой новый прыжок — это либо прыжок в отца, либо комбинация двух одинаковых прыжков. Тогда если те прыжки имели длину, равную степени двойки, то и комбинация тоже.
Однако в отличие от обычных двоичных подъемов, в которых мы постепенно уменьшали длину прыжка, здесь все немного сложнее. Сначала длина прыжка постепенно увеличивается, а потом постепенно уменьшается. Это чем-то похоже на путешествие между городами. Сначала мы едем по маленьким улочкам, постепенно выезжая на более широкие проспекты, в конце концов выезжаем на шоссе, а в конце пути происходит симметричная ситуация: мы съезжаем с магистралей на проспекты, а с проспектов на узкие улочки.
Давайте разделим наш путь на две части: сначала длины прыжков постепенно возрастают, и мы всегда используем прыжок, потом в какой-то момент прыжок ведет в слишком высокую вершину, поэтому нам приходится использовать переход в отца, после чего мы будем иногда использовать переходы в отцов, а иногда прыжки, но длины прыжков будут не возрастать.
Докажем несколько утверждений.
Теорема: Прыжки не пересекаются (но один может лежать строго внутри другого).
Доказательство:
Докажем это утверждение по индукции. Пусть это утверждение верно для всех предков текущей вершины, докажем для прыжка из текущей вершины. Если прыжок ведет в отца, то такой прыжок, очевидно, не может ни с кем пересекаться. Если же прыжок ведет не в отца, то он является комбинацией двух прыжков. Если какой-то прыжок пересекается с новым прыжком, то он пересекается и с одним из двух меньших прыжков. Но для них мы уже доказали по предположению индукции, что они попарно не пересекаются.
Теорема: Не может быть больше двух одинаковых прыжков подряд, то есть не может быть так, что длины прыжков из v, jump[v] и jump[jump[v]] совпадают.
Доказательство:
Действительно, если бы они все совпадали, то прыжок из сына jump[v] вел бы в jump[jump[v]], потому что прыжки его предков равны по длине. А тогда этот прыжок бы пересекался с прыжком из $v$, что невозможно по предыдущей теореме.
Крайним случаем будет ситуация, когда длины всех трех прыжков равны единице, однако в этой ситуации из v прыжок должен вести в jump[jump[v]], а не в jump[v], что противоречит условию.
Теорема: Длина прыжка из v не больше длины прыжка из jump[v] в том случае, если jump[v] — это не корень. То есть если мы переходим по прыжкам, то их длины не убывают.
Доказательство: Действительно, если наш прыжок ведет в корень, то оттуда уже некуда прыгать. А иначе прыжок будет иметь не меньшую длину.
Докажем это утверждение по индукции. Пусть это утверждение верно для всех предков текущей вершины, докажем для прыжка из текущей вершины. Если этот прыжок ведет в отца, то это самый маленький возможный прыжок, и следующий точно не меньше. Если же прыжок ведет не в отца, то он был получен из двух меньших прыжков длины в два раза меньше, Тогда так как для всех предков утверждение уже верно, то прыжок из нашего прыжка точно не может быть короче нашего прыжка более, чем в два раза. Однако если он короче ровно в два раза, то мы получаем три последовательных прыжка одинаковой длины, чего не бывает по предыдущей теореме. Поэтому прыжок из нашего прыжка имеет длину не меньше, чем текущий прыжок.
Из этих утверждений легко понять, что первая фаза путешествия, в которой мы всегда переходим по прыжкам, работает за логарифмическое время. Действительно, длина прыжка не убывает, но при этом она не может оставаться фиксированной более, чем два раза, поэтому через $2 \log n$ итераций длина прыжка станет не меньше $n$, и в этот момент прыжок уже точно будет выше, чем необходимая нам вершина.
На второй же фазе путешествия мы пытаемся получить точную вершину, в которую нам нужно прийти. нам не подходит прыжок длины $2^k$, то есть наша вершина находится между текущей вершиной и прыжком из нее. Тогда мы переходим в нашего отца, в результате чего отрезок, на котором мы ищем, поделился на два. И если нужная вершина находится в верхней половине, то мы сделаем прыжок из нашего отца, а если в нижней, то не сделаем. В любом случае, через каждые два шага длина прыжка из текущей вершины будет уменьшаться в два раза, и таким бинпоиском мы постепенно придем в нужную вершину.
Поиск предка на глубине $h$
Доказательство не совсем очевидно, однако его не нужно помнить, чтобы применять эту структуру данных. Давайте рассмотрим пример ее работы для задачи LA (level ancestor), то есть поиска предка текущей вершины на глубине $h$. Для этого мы постепенно идем наверх, пытаясь пойти в прыжок текущей вершины, если его глубина не меньше $h$, а в противном случае идем в отца.
С реализацией можно ознакомиться по ссылке.
Асимптотика ответа на $q$ запросов на дереве из $n$ вершин будет $O(n + q \log n)$.
Поиск наименьшего общего предка
Теперь рассмотрим другую задачу, для решения которой обычно используют бинарные подъемы: LCA (least common ancestor или наименьший общий предок). Воспользуемся следующей идеей: сначала из более глубокой вершины перейдем на глубину менее глубокой при помощи LA, а затем будем параллельно подниматься наверх из двух вершин. Обратите внимание на то, что если две вершины находятся на одной и той же глубине, то длины их прыжков совпадают, поэтому мы можем переходить по прыжку в том случае, если концы этих прыжков не равны, а в противном случае переходить в отца.
С реализацией можно ознакомиться по ссылке.
Асимптотика ответа на $q$ запросов на дереве из $n$ вершин будет $O(n + q \log n)$.
Также аналогично двоичным подъемам можно хранить значение какой-то функции на прыжке и при помощи этого искать значение функции на пути в дереве.
Задачи для практики
Для практики подойдут любые задачи на двоичные подъемы и LCA.