Информатика / Алгоритмы и анализ данных
Наименьший общий предок двоичным подъёмом
Двоичный подъём отвечает на запрос LCA двух вершин дерева через таблицу предков 2^k. После DFS построение занимает O(n log n), один запрос — O(log n).
Формула
Вершины 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), а проверка принадлежности одной компоненте защищает от фиктивных ответов через нулевого предка.
Как пользоваться формулой
- Выберите корень, выполните DFS или BFS и сохраните depth[v] и непосредственного родителя up[v][0] для каждой вершины.
- Заполните up[v][k] по формуле up[v][k]=up[up[v][k−1]][k−1] для k от 1 до LOG−1.
- Если depth[u] меньше depth[v], поменяйте вершины и поднимите u на depth[u]−depth[v] по установленным битам.
- При несовпадении вершин перебирайте k от LOG−1 до 0 и поднимайте обе, когда up[u][k] и up[v][k] различны.
- Если после выравнивания вершины совпали, верните эту вершину; иначе после совместного подъёма верните 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/
Связанные формулы
Информатика
Поиск в глубину: дерево обхода и времена входа и выхода
Поиск в глубину, или DFS, полностью исследует одну ветвь графа перед возвратом к следующей. Времена входа и выхода образуют вложенные интервалы и позволяют проверять родство в дереве обхода.
Информатика
Поиск в ширину: кратчайший путь по числу рёбер
Поиск в ширину, или BFS, находит минимальное число переходов от стартовой вершины в невзвешенном графе. Очередь обрабатывает вершины слоями, поэтому первое открытие уже задаёт кратчайшее расстояние.
Информатика
Топологическая сортировка Кана по входящим степеням
Алгоритм Кана упорядочивает вершины ориентированного графа, последовательно выбирая вершину без входящих дуг. Если вывести все вершины не удалось, оставшаяся часть содержит ориентированный цикл.