Двоичный подъём (binary lifting): k-й предок, LCA и прыжки за O(log n)

Двоичный подъём простыми словами: таблица предков up[k][v], k-й предок за O(log n), LCA, максимум на пути, поиск по предкам и k шагов в функциональном графе. Код на Python.

13 мин чтенияалгоритмы · деревья · python

Коротко

ЧтоСложность
Построение таблицы up[k][v]O(nlog⁡n)O(n \log n) времени и памяти
k-й предок вершиныO(log⁡n)O(\log n)
LCA двух вершинO(log⁡n)O(\log n)
Максимум/сумма на путиO(log⁡n)O(\log n)
k шагов в функциональном графеO(log⁡k)O(\log k)
  • Идея: для каждой вершины заранее запоминаем, куда она попадает через 1, 2, 4, 8, … шагов вверх. Любое число шагов — сумма степеней двойки, то есть его двоичная запись.
  • Рекуррентность: up[k][v]=up[k−1][ up[k−1][v] ]up[k][v] = up[k-1][\,up[k-1][v]\,] — прыжок на 2k2^k равен двум прыжкам на 2k−12^{k-1}.
  • Где нужно: много запросов «подняться на k», LCA, агрегаты на пути в дереве, «где я окажусь через 101810^{18} ходов».

Если вас интересует именно LCA и сравнение способов его искать (наивный подъём, эйлеров обход + RMQ, Тарьян), это отдельная статья — наименьший общий предок. Здесь — сама техника двоичного подъёма: что ещё она умеет и как не ошибиться в реализации.

Задача, с которой всё начинается

Дано корневое дерево из nn вершин в виде массива родителей: parent[v] — родитель v, у корня -1. Нужно отвечать на запросы «кто k-й предок вершины v?» — то есть кто окажется на месте v, если подняться на k рёбер вверх.

Это ровно задача LeetCode 1483 «Kth Ancestor of a Tree Node». Там до 5⋅1045 \cdot 10^4 вершин и столько же запросов.

Наивно: шагаем по одному

def kth_ancestor_naive(parent: list[int], v: int, k: int) -> int: while k and v != -1: v = parent[v] k -= 1 return v

Запрос стоит O(k)O(k), а kk может быть порядка nn. На дереве-«бамбуке» (цепочке) получаем O(n⋅q)O(n \cdot q) — 2.5⋅1092.5 \cdot 10^9 шагов на ограничениях задачи. Не проходит.

Другая крайность: хранить всех предков

Можно для каждой вершины сохранить список всех её предков и отвечать за O(1)O(1). Но на цепочке это n2/2n^2/2 чисел — больше миллиарда. Тоже не годится.

Двоичный подъём — компромисс между этими крайностями: храним не всех предков, а только тех, что стоят на расстояниях 1,2,4,…,2log⁡n1, 2, 4, \dots, 2^{\log n}. Это log⁡n\log n чисел на вершину, а любой подъём собирается из них за log⁡n\log n прыжков.

Таблица предков

Заведём таблицу up[k][v] — предок вершины v на расстоянии 2k2^k (или -1, если дерево кончилось).

  • Слой k = 0 — это просто массив родителей.
  • Слой k строится из слоя k − 1: чтобы прыгнуть на 2k2^k, прыгаем на 2k−12^{k-1}, а потом ещё раз на 2k−12^{k-1}.

up[k][v]=up[k−1][ up[k−1][v] ]up[k][v] = up[k-1][\,up[k-1][v]\,]

По сути это разреженная таблица, только «отрезки» лежат не в массиве, а на путях к корню. Если вы читали про Sparse Table, узнаете ту же идею: перекрывать всё степенями двойки и собирать большое из двух половин.

Разбор на примере

        0
       / \
      1   2
     / \   \
    3   4   5
        |
        6
        |
        7

parent = [-1, 0, 0, 1, 1, 2, 4, 6]. Таблица:

k \ v01234567
0 (на 1 вверх)−10011246
1 (на 2 вверх)−1−1−100014
2 (на 4 вверх)−1−1−1−1−1−1−10

Проверим одну клетку: up[1][7] = up[0][ up[0][7] ] = up[0][6] = 4. Действительно, на два уровня выше вершины 7 стоит 4.

Запрос «3-й предок вершины 7»: 3=20+213 = 2^0 + 2^1, то есть 011 в двоичной записи.

  1. Бит 0 установлен: 7 → up[0][7] = 6.
  2. Бит 1 установлен: 6 → up[1][6] = 1.

Ответ — 1. Проверяем по картинке: 7 → 6 → 4 → 1. Сошлось.

Порядок прыжков при подъёме на k неважен — в каком порядке ни складывай слагаемые, сумма одна. Это отличает k-й предок от второго этапа LCA, где порядок «от больших к меньшим» обязателен.

Реализация: k-й предок

class TreeAncestor: def __init__(self, n: int, parent: list[int]) -> None: self.LOG = max(1, n.bit_length()) # up[k][v] — предок v на 2^k выше, -1 если такого нет self.up = [parent[:]] for k in range(1, self.LOG): prev = self.up[k - 1] self.up.append([-1 if prev[v] == -1 else prev[prev[v]] for v in range(n)]) def getKthAncestor(self, node: int, k: int) -> int: if k >= 1 << self.LOG: return -1 for j in range(self.LOG): if k >> j & 1: node = self.up[j][node] if node == -1: return -1 return node parent = [-1, 0, 0, 1, 1, 2, 4, 6] ta = TreeAncestor(8, parent) print(ta.getKthAncestor(7, 1)) # 6 print(ta.getKthAncestor(7, 3)) # 1 print(ta.getKthAncestor(7, 4)) # 0 print(ta.getKthAncestor(7, 5)) # -1 print(ta.getKthAncestor(5, 2)) # 0

Несколько решений, которые здесь приняты сознательно.

LOG = n.bit_length(). Глубина дерева не больше n−1n - 1, а n−1<2bit_length(n)n - 1 < 2^{\text{bit\_length}(n)}. Значит любого предка можно достать прыжками по слоям 0 … LOG − 1. Если k больше — предка точно нет, отвечаем сразу.

Слои строятся целиком, внешний цикл по k. В LeetCode 1483 не гарантируется, что родитель имеет номер меньше ребёнка. Если идти по вершинам и для каждой заполнять все k сразу, можно обратиться к up[k−1][p] вершины p, которую ещё не посчитали. Когда внешний цикл по слоям, слой k − 1 всегда готов полностью — порядок вершин не важен.

Раскладка up[k][v], а не up[v][k]. В Python это LOG списков длины n вместо n списков длины LOG: меньше объектов, и слой удобно строить одним списковым включением. В C++ и Java такая раскладка тоже обычно быстрее при построении — проход по слою идёт подряд по памяти.

-1 как «за корнем». Альтернатива — считать родителем корня сам корень. Тогда прыжки «упираются» в корень и никогда не выходят за границы массива. Это удобно для LCA, но для k-го предка придётся отдельно проверять глубину: иначе на запрос «10-й предок» вернётся корень вместо -1.

Сложность

  • Построение: n⋅log⁡nn \cdot \log n операций и столько же памяти. Для n=2⋅105n = 2 \cdot 10^5 это примерно 3.6⋅1063.6 \cdot 10^6 чисел — нормально даже для Python.
  • Запрос: не больше LOG прыжков, то есть O(log⁡n)O(\log n).

Для работы с битами k >> j & 1 пригодятся приёмы из статьи про битовые операции.

LCA через ту же таблицу

Самое известное применение. Подробно с разбором и сравнением методов — в статье про LCA, здесь только схема:

  1. Поднять более глубокую вершину на разницу глубин — это k-й предок.
  2. Если вершины совпали — одна была предком другой, ответ найден.
  3. Иначе идти по k от большего к меньшему и прыгать обеими вершинами, пока их предки на 2k2^k различаются. В конце обе стоят прямо под LCA, ответ — их родитель.

Для LCA удобнее, чтобы родителем корня был сам корень, и нужен массив глубин. Поэтому дальше используем такую версию.

Максимум на пути: таблица не только вершин

Двоичный подъём умеет больше, чем «куда я попаду». Вместе с up[k][v] можно хранить любую ассоциативную величину на отрезке пути длины 2k2^k: максимум, минимум, сумму, НОД. Пересчёт тот же — из двух половин:

mx[k][v]=max⁡(mx[k−1][v], mx[k−1][ up[k−1][v] ])mx[k][v] = \max(mx[k-1][v],\ mx[k-1][\,up[k-1][v]\,])

Классическая задача: дано взвешенное дерево, запрос — максимальный вес ребра на пути между u и v. Путь разбивается в LCA на два вертикальных куска, каждый проходим подъёмом и собираем максимум.

from collections import deque class BinaryLifting: def __init__(self, n: int, edges: list[tuple[int, int, int]], root: int = 0) -> None: graph = [[] for _ in range(n)] for u, v, w in edges: graph[u].append((v, w)) graph[v].append((u, w)) self.LOG = max(1, n.bit_length()) parent = [root] * n # родитель корня — сам корень weight = [0] * n # вес ребра до родителя self.depth = [0] * n # BFS вместо рекурсии: глубина дерева может быть 10^5 seen = [False] * n seen[root] = True queue = deque([root]) while queue: v = queue.popleft() for to, w in graph[v]: if not seen[to]: seen[to] = True parent[to] = v weight[to] = w self.depth[to] = self.depth[v] + 1 queue.append(to) # up[k][v] — предок на 2^k выше, mx[k][v] — максимум рёбер на этом отрезке self.up = [parent] self.mx = [weight] for k in range(1, self.LOG): up_prev, mx_prev = self.up[-1], self.mx[-1] self.up.append([up_prev[up_prev[v]] for v in range(n)]) self.mx.append([max(mx_prev[v], mx_prev[up_prev[v]]) for v in range(n)]) def lift(self, v: int, k: int) -> tuple[int, int]: """Поднимает v на k уровней, возвращает (вершину, максимум рёбер по пути).""" best = 0 j = 0 while k: if k & 1: best = max(best, self.mx[j][v]) v = self.up[j][v] k >>= 1 j += 1 return v, best def lca(self, u: int, v: int) -> int: if self.depth[u] < self.depth[v]: u, v = v, u u, _ = self.lift(u, self.depth[u] - self.depth[v]) if u == v: return u for k in range(self.LOG - 1, -1, -1): if self.up[k][u] != self.up[k][v]: u, v = self.up[k][u], self.up[k][v] return self.up[0][u] def path_max(self, u: int, v: int) -> int: a = self.lca(u, v) _, left = self.lift(u, self.depth[u] - self.depth[a]) _, right = self.lift(v, self.depth[v] - self.depth[a]) return max(left, right) # 0 # 4/ \1 # 1 2 # 2/ \7 \3 # 3 4 5 # |5 # 6 edges = [(0, 1, 4), (0, 2, 1), (1, 3, 2), (1, 4, 7), (2, 5, 3), (4, 6, 5)] bl = BinaryLifting(7, edges) print(bl.lca(6, 3)) # 1 print(bl.lca(6, 5)) # 0 print(bl.path_max(6, 3)) # 7 → путь 6-4-1-3, рёбра 5, 7, 2 print(bl.path_max(3, 5)) # 4 → путь 3-1-0-2-5, рёбра 2, 4, 1, 3

Обратите внимание: у корня weight = 0, а up указывает на себя. Прыжок «за корень» добавляет к максимуму ноль и остаётся на месте, поэтому ничего не ломает. С суммой так тоже работает, с минимумом — нет: ноль испортит ответ, и нейтральным элементом для корня должна быть +∞+\infty.

Где это встречается: «максимальное ребро на пути в минимальном остовном дереве» — основа задач про второе по весу остовное дерево и про проверку, войдёт ли новое ребро в MST.

Важное ограничение: таблица статическая. Если веса рёбер меняются между запросами, пересчитывать её дорого — тут нужны heavy-light decomposition и дерево отрезков.

Двоичный поиск по предкам

Второй приём, который часто упускают. Если вдоль пути к корню какое-то свойство монотонно, двоичный подъём находит границу за O(log⁡n)O(\log n) — это двоичный поиск, только по предкам.

Пример: дерево коммитов, у каждого коммита время создания. Родитель всегда старше ребёнка, значит при подъёме время убывает. Запрос: «самый старый предок коммита v, сделанный не раньше момента t».

Жадность та же, что во втором этапе LCA: идём от больших прыжков к меньшим и прыгаем, если после прыжка условие ещё выполняется.

def oldest_since(up: list[list[int]], time: list[int], v: int, t: int) -> int: """Самый далёкий предок v (включая v), чей time >= t. Время растёт сверху вниз.""" if time[v] < t: return -1 for k in range(len(up) - 1, -1, -1): a = up[k][v] if a != -1 and time[a] >= t: v = a return v # коммиты: 0 ← 1 ← 2 ← 3 ← 4, 2 ← 5 parent = [-1, 0, 1, 2, 3, 2] time = [100, 140, 150, 210, 230, 160] LOG = len(parent).bit_length() up = [parent] for k in range(1, LOG): prev = up[-1] up.append([-1 if prev[v] == -1 else prev[prev[v]] for v in range(len(parent))]) print(oldest_since(up, time, 4, 145)) # 2 → 4, 3, 2 новее 145, а 1 уже старше print(oldest_since(up, time, 5, 90)) # 0 print(oldest_since(up, time, 5, 200)) # -1

Почему это корректно. Пусть ответ лежит на расстоянии dd от v. Перебирая k сверху вниз, мы прыгаем ровно тогда, когда 2k2^k ещё помещается в оставшуюся часть dd, — так жадно собирается двоичная запись dd. Монотонность гарантирует, что «условие выполнено после прыжка» равносильно «не перепрыгнули ответ».

Если свойство не монотонно само по себе, его часто можно сделать монотонным через агрегат. «Подняться как можно выше, чтобы все вершины по пути были не больше x» — монотонно, даже если значения скачут: достаточно хранить максимум на отрезке, как в разделе выше, и прыгать, пока он не больше x.

Функциональный граф: k шагов, когда k огромно

Двоичному подъёму не нужно дерево. Достаточно, чтобы из каждой вершины вёл ровно один переход — f[x]. Такой граф называют функциональным: это набор циклов, к которым подвешены деревья. Связный список с циклом — его частный случай, и алгоритм Флойда работает именно с такой структурой.

Задача: «фишка стоит в клетке x, за ход переходит в f[x]. Где она окажется через k=1018k = 10^{18} ходов?». Моделировать нельзя, а двоичный подъём справляется за 60 прыжков — по числу битов в kk.

def build_jumps(f: list[int], max_k: int) -> list[list[int]]: jumps = [f] for _ in range(max_k.bit_length() - 1): prev = jumps[-1] jumps.append([prev[prev[x]] for x in range(len(f))]) return jumps def walk(jumps: list[list[int]], x: int, k: int) -> int: j = 0 while k: if k & 1: x = jumps[j][x] k >>= 1 j += 1 return x f = [1, 2, 3, 4, 2, 0] # 5 → 0 → 1 → 2 → 3 → 4 → 2 → ... jumps = build_jumps(f, 10**18) print(len(jumps)) # 60 print(walk(jumps, 5, 4)) # 3 print(walk(jumps, 5, 10**18)) # 3

Два отличия от дерева:

  • Число слоёв определяется максимальным k, а не числом вершин. Здесь LOG = 60, хотя вершин шесть.
  • Значения -1 нет: переход всегда существует, поэтому и проверка не нужна.

К прыжкам по функциональному графу так же можно добавить агрегат. Например, сумма номеров всех посещённых клеток за k ходов — это LeetCode 2836 «Maximize Value of Function in a Ball Passing Game». Там хранят sum[k][x] рядом с jumps[k][x] и пересчитывают из двух половин.

Альтернатива для одного запроса — найти цикл, длину предпериода и взять остаток от деления. Это O(n)O(n) без таблицы, но на каждый новый старт придётся искать заново. Двоичный подъём выигрывает, когда запросов много.

Когда двоичный подъём не нужен

Техника универсальная, но не всегда лучшая.

СитуацияЧто лучше
Все запросы известны заранееОдин DFS с текущим путём в стеке: k-й предок — path[-1 - k], O(1)O(1) на запрос и O(n)O(n) памяти
Нужен LCA за O(1)O(1) на запросЭйлеров обход + Sparse Table
Нужен k-й предок за O(1)O(1) онлайнLadder-алгоритм (Bender, Farach-Colton): лестницы поверх тех же прыжков
Веса на пути меняютсяHeavy-light decomposition + дерево отрезков
Мало памяти, nn порядка 10710^7Skew-binary jump pointers: один указатель на вершину, запрос по-прежнему за O(log⁡n)O(\log n)

Офлайн-вариант настолько прост, что о нём стоит помнить в первую очередь:

def kth_ancestors_offline(children: list[list[int]], root: int, queries: list[tuple[int, int]]) -> list[int]: by_node = [[] for _ in children] for i, (v, k) in enumerate(queries): by_node[v].append((i, k)) answer = [-1] * len(queries) path = [] # текущий путь от корня stack = [(root, False)] while stack: v, done = stack.pop() if done: path.pop() # выходим из вершины continue path.append(v) for i, k in by_node[v]: if k < len(path): answer[i] = path[-1 - k] stack.append((v, True)) for c in children[v]: stack.append((c, False)) return answer children = [[1, 2], [3, 4], [5], [], [6], [], [7], []] print(kth_ancestors_offline(children, 0, [(7, 1), (7, 3), (7, 5), (5, 2)])) # [6, 1, -1, 0]

Итеративный обход в глубину с пометкой «вышли из вершины» поддерживает путь от корня до текущей вершины. Пока мы в v, все её предки лежат в path по порядку.

Частые ошибки

Мало слоёв. LOG должен покрывать максимальную глубину (или максимальное k в функциональном графе). int(math.log2(n)) без +1 теряет старший слой. Надёжнее n.bit_length(): для любого k < n этого достаточно.

Заполнение по вершинам, а не по слоям. Цикл «для каждой вершины — все k» корректен, только если родитель обработан раньше ребёнка (порядок BFS/DFS). Для произвольной нумерации — внешний цикл по k.

Выход за корень. С -1 нужно проверять результат каждого прыжка, иначе prev[-1] в Python тихо возьмёт последний элемент списка и вернёт мусор вместо ошибки. Это коварный баг: тесты на маленьких деревьях часто проходят.

Корень-сам-себе-родитель в задаче про k-го предка. Прыжки не выходят за границы, но «20-й предок» вершины глубины 3 окажется корнем. Нужна проверка k > depth[v].

Неверный нейтральный элемент агрегата. Ноль для минимума, единица для суммы — ответ съезжает на путях, проходящих через корень.

Рекурсия на глубоком дереве. Цепочка из 10510^5 вершин уронит рекурсивный DFS в Python. Строить родителей и глубины — итеративно, BFS или стеком.

Порядок битов в LCA и поиске. Подъём на ровно k шагов можно делать в любом порядке битов. А «прыгай, пока условие выполнено» — только от больших степеней к меньшим.

Как спрашивают на собеседованиях

На обычных секциях в продуктовых компаниях двоичный подъём встречается нечасто: это скорее «хард» и олимпиадная техника. Но есть типичные сценарии.

  • Kth Ancestor of a Tree Node (LeetCode 1483) — прямая формулировка. Ожидают, что вы начнёте с наивного O(k)O(k), оцените его на худшем случае (цепочка) и придёте к таблице.
  • LCA с множеством запросов. Если интервьюер просит LCA один раз — хватит обычного рекурсивного обхода. Если запросов 10510^5 — это сигнал к двоичному подъёму.
  • «Где окажемся через k шагов», k до 101810^{18} — функциональный граф. Узнаётся по огромному k и одному переходу из каждого состояния.
  • Вопрос на понимание: «почему O(nlog⁡n)O(n \log n) памяти, а не O(n2)O(n^2)?» и «почему подъём на k — это двоичная запись k?». Ответ из двух предложений показывает, что вы понимаете технику, а не заучили код.

Хороший порядок ответа: наивное решение → его сложность на цепочке → идея степеней двойки → рекуррентность → запрос по битам → сложность → крайние случаи (корень, k больше глубины).

Что запомнить

  • Двоичный подъём — таблица up[k][v]: куда попадёт v через 2k2^k шагов. Строится по слоям: up[k][v]=up[k−1][up[k−1][v]]up[k][v] = up[k-1][up[k-1][v]].
  • Подъём на k — прыжки по установленным битам k, O(log⁡n)O(\log n).
  • Рядом с переходами можно хранить ассоциативный агрегат на отрезке: максимум, минимум, сумму.
  • Монотонное условие на пути к корню ищется жадно, от больших прыжков к меньшим, — это двоичный поиск по предкам.
  • Дерево не обязательно: хватает одного перехода из каждой вершины. Тогда число слоёв задаёт максимальное k.
  • Если все запросы известны заранее, часто проще один DFS с путём в стеке.

Потренироваться в спокойной обстановке

Все задачи