Информатика / Алгоритмы и анализ данных

Наименьший общий предок двоичным подъёмом

Двоичный подъём отвечает на запрос LCA двух вершин дерева через таблицу предков 2^k. После DFS построение занимает O(n log n), один запрос — O(log n).

Опубликовано: Обновлено:

Формула

$$up[v][0]=parent(v),\quad up[v][k]=up[up[v][k-1]][k-1],\quad up[root][k]=root$$
Схема Двоичный подъём к LCA
1234567LCA(4,6)=1

Вершины 4 и 6 поднимаются к разным детям корня, затем ответом становится 1.

Обозначения

$up[v][k]$
предок v на расстоянии 2^k рёбер, вершина
$depth[v]$
расстояние от корня до v, ребро
$u,v$
вершины запроса, вершина
$LOG$
число уровней таблицы, уровень
$n$
Число вершин в дереве, —
$k$
Номер степени двойки от 0 до LOG − 1, —
$root$
Выбранный корень дерева; его родитель — он сам, вершина
$parent(v)$
Непосредственный родитель v, вершина

Условия применения

Граф должен быть деревом или лесом с выбранным корнем каждой компоненты. Глубины измеряют рёбрами, корень имеет глубину 0, а ancestor[v][0] — непосредственного родителя. Для леса запрос между компонентами должен быть отвергнут или обработан отдельно. Во всех строках таблицы предок корня — сам корень. Число столбцов LOG = floor(log₂n) + 1 при n ≥ 1.

Ограничения

Таблица требует O(n log n) памяти и предварительного обхода; частые изменения рёбер требуют другой структуры. Метод возвращает LCA только в корневом дереве, а не общего предка в произвольном ориентированном графе. Неверный корень меняет ответ, хотя дерево как неориентированный граф остаётся тем же.

Подробное объяснение

Наименьший общий предок двух вершин — самый глубокий узел, лежащий на обоих корневых путях. Если одна вершина уже лежит на пути от другой к корню и служит предком другой, ответом будет она сама. Поэтому глубины и направление к корню входят в определения запроса.

Таблица up строится рекуррентно: предок на 2^k шагах получается как предок предка на 2^(k−1) шагах. После DFS известен up[v][0], а затем каждая строка заполняется снизу вверх по степеням двойки.

Сначала выравнивают глубины: более глубокую вершину поднимают на разность глубин, раскладывая число по битам. Если вершины совпали, ранний ответ уже найден. Иначе их одновременно поднимают от большого k к малому, выполняя прыжок только тогда, когда предки различны.

После такого спуска u и v — разные дети искомого узла, а up[u][0] и up[v][0] совпадают с LCA. Обратный порядок степеней важен: крупный прыжок безопасен только пока он не пересекает границу общего предка.

При n вершинах достаточно LOG=floor(log₂n)+1 столбцов, включая k=0. Предобработка DFS и таблицы стоит O(n log n), запросы занимают O(log n), а проверка принадлежности одной компоненте защищает от фиктивных ответов через нулевого предка.

Как пользоваться формулой

  1. Выберите корень, выполните DFS или BFS и сохраните depth[v] и непосредственного родителя up[v][0] для каждой вершины.
  2. Заполните up[v][k] по формуле up[v][k]=up[up[v][k−1]][k−1] для k от 1 до LOG−1.
  3. Если depth[u] меньше depth[v], поменяйте вершины и поднимите u на depth[u]−depth[v] по установленным битам.
  4. При несовпадении вершин перебирайте k от LOG−1 до 0 и поднимайте обе, когда up[u][k] и up[v][k] различны.
  5. Если после выравнивания вершины совпали, верните эту вершину; иначе после совместного подъёма верните up[u][0].

Историческая справка

Задача о наименьшем общем предке относится к классическим запросам в корневых деревьях. Прямой подъём по одному ребру может занимать время, пропорциональное высоте дерева. Двоичный подъём сохраняет предков на расстояниях степеней двойки и использует разложение расстояния по битам.

В современных университетских материалах binary lifting рассматривают как прозрачный способ получить логарифмический запрос после предварительной обработки. Его таблица строится тем же приёмом удвоения, который применим к многократному выполнению функции: два перехода длины 2^(k−1) дают переход длины 2^k.

В литературе существуют и другие подходы к LCA: обход Эйлера с запросами минимума на отрезке, пакетный алгоритм Тарьяна и методы для динамических деревьев. Наличие этих вариантов не меняет определения общего предка, но меняет требования к памяти, режиму запросов и допустимым изменениям дерева. Здесь авторство всей техники одному человеку не приписывается.

Пример

Рассмотрим рёбра 1–2, 1–3, 2–4, 2–5, 3–6 и 3–7; корень — 1. Глубины: depth(4)=depth(5)=2, depth(6)=depth(7)=2. Таблица первых предков хранит up[4][0]=2 и up[6][0]=3. Для запроса LCA(4,6) глубины равны. На уровне k=1 предки равны 1, поэтому прыжок 2^1 нельзя делать: он сразу пересечёт ответ. На k=0 предки 2 и 3 различны, значит поднимаем обе вершины на один шаг. После подъёма получаем 2 и 3; их непосредственный общий родитель — 1. Следовательно, LCA(4,6)=1. Для LCA(4,5) алгоритм видит, что up[4][0]=2 и up[5][0]=2, поэтому ответом остаётся 2, а не корень.

Частая ошибка

Не путайте LCA с первым общим предком в списке родителей: нужен самый глубокий. Ошибка в глубине на один уровень ломает выравнивание. Нельзя поднимать обе вершины, когда их предки совпадают, иначе перескочите через ответ. Для корня задайте безопасного предка и отдельно проверяйте компоненты, чтобы нулевая вершина не стала ложным LCA.

Практика

Задачи с решением

Общий родитель

Условие. В дереве 1–2, 1–3, 2–4, 2–5, 3–6 найдите LCA(4,5).

Решение. Обе вершины имеют глубину 2 и общего непосредственного родителя 2.

Ответ. 2

Через корень

Условие. В том же дереве найдите LCA(4,6).

Решение. Предки перед подъёмом 2 и 3 различны; после подъёма общий родитель равен 1.

Ответ. 1

Дополнительные источники

  • https://cp-algorithms.com/graph/lca_binary_lifting.html
  • https://cs491-web-fa24.pages.dev/lectures/lca_binary_lifting/

Связанные формулы

Информатика

Поиск в глубину: дерево обхода и времена входа и выхода

$u\text{ — предок }v\iff t_{in}(u)<t_{in}(v)<t_{out}(v)<t_{out}(u),\quad u\ne v$

Поиск в глубину, или DFS, полностью исследует одну ветвь графа перед возвратом к следующей. Времена входа и выхода образуют вложенные интервалы и позволяют проверять родство в дереве обхода.

Информатика

Поиск в ширину: кратчайший путь по числу рёбер

$d(s)=0,\qquad d(v)=d(u)+1\quad\text{при первом открытии }v\text{ из }u$

Поиск в ширину, или BFS, находит минимальное число переходов от стартовой вершины в невзвешенном графе. Очередь обрабатывает вершины слоями, поэтому первое открытие уже задаёт кратчайшее расстояние.

Информатика

Топологическая сортировка Кана по входящим степеням

$d_{in}(v)\leftarrow d_{in}(v)-1\quad\text{при удалении дуги }u\to v;\qquad |L|=|V|\iff G\text{ ацикличен}$

Алгоритм Кана упорядочивает вершины ориентированного графа, последовательно выбирая вершину без входящих дуг. Если вывести все вершины не удалось, оставшаяся часть содержит ориентированный цикл.