LCA через двоичные подъёмы (binary lifting): как считать up[v][k] и подниматься?
Нужен наименьший общий предок (LCA) двух вершин дерева, запросов много (до 10^5). Понял, что наивный подъём по одному предку — O(глубины) на запрос, это медленно. Слышал про двоичные подъёмы. Как устроена таблица up[v][k] (2^k-й предок) и как ей пользоваться для LCA?
2 ответа
Предподсчёт. up[v][k] = предок вершины v на 2^k уровней выше. База: up[v][0] = непосредственный родитель. Переход: up[v][k] = up[ up[v][k-1] ][k-1] (подняться на 2^(k-1), потом ещё на 2^(k-1)). Также храним глубины depth[v].
const int LOG = 20; // 2^20 > 10^6
int up[N][LOG], depth[N];
vector<int> g[N];
void dfs(int v, int p) {
up[v][0] = p;
for (int k = 1; k < LOG; k++)
up[v][k] = up[ up[v][k-1] ][k-1];
for (int u : g[v]) if (u != p) {
depth[u] = depth[v] + 1;
dfs(u, v);
}
}
int lca(int a, int b) {
if (depth[a] < depth[b]) swap(a, b);
int d = depth[a] - depth[b];
for (int k = 0; k < LOG; k++) // поднять a до уровня b
if (d & (1 << k)) a = up[a][k];
if (a == b) return a;
for (int k = LOG - 1; k >= 0; k--) // прыгаем вверх, пока предки РАЗНЫЕ
if (up[a][k] != up[b][k]) { a = up[a][k]; b = up[b][k]; }
return up[a][0]; // ответ — на 1 выше
}
Сложность: предподсчёт O(V·log V), запрос O(log V). Память O(V·log V).
Ключ во второй фазе: прыгаем сверху вниз по битам и поднимаемся, только если предки различаются — так останавливаемся ровно под LCA, а up[a][0] и есть сам LCA. Корню в качестве up[root][k] ставьте сам корень (или фиктивную вершину), чтобы не вылезти за дерево.
Полезный бонус binary lifting: помимо LCA почти бесплатно считается расстояние между вершинами dist(a,b) = depth[a] + depth[b] - 2*depth[lca(a,b)] и k-й предок за O(log). Это часто требуется в задачах на деревья (k-я вершина на пути и т.п.).
Грабля по памяти: при V=2·10^5 и LOG=20 таблица int up[N][LOG] = 1.6·10^7 int ≈ 64 МБ — впритык к лимитам. Если тесно — берите LOG ровно по максимуму (ceil(log2(maxN))), а не с запасом, или храните up как vector<array<int,LOG>>. Альтернатива с меньшей памятью — LCA через Эйлеров обход + разреженную таблицу RMQ (O(1) на запрос, O(V log V) память тоже, но другой константой).