LCA через Эйлеров обход и RMQ за O(1) на запрос — как свести задачу к минимуму на отрезке?
Видел, что LCA можно решать за O(1) на запрос через Эйлеров обход дерева и RMQ (минимум на отрезке). Не понимаю, как обход дерева превращает LCA в задачу про минимум на подотрезке массива. Можете объяснить сведение и дать реализацию через разреженную таблицу?
2 ответа
Сведение. Делаем Эйлеров обход: записываем вершину в массив euler каждый раз, когда DFS заходит в неё или возвращается в неё. Параллельно пишем глубины. Для каждой вершины запоминаем first[v] — первое её появление в euler.
Ключ: LCA(a,b) — это вершина минимальной глубины в euler на отрезке между first[a] и first[b]. Почему — потому что между двумя появлениями любых вершин обход обязательно «всплывает» до их общего предка, и самая высокая (минимальная глубина) вершина на этом куске и есть LCA.
Теперь это RMQ по глубине. На статичном массиве — разреженная таблица (sparse table): предподсчёт O(M log M), запрос O(1):
vector<int> euler, depthE; vector<int> first_; // first_[v]
// заполняем DFS-ом: при входе и после каждого возврата push в euler/depthE
int M; vector<vector<int>> sp; // sp[k][i] = индекс мин глубины на [i, i+2^k)
void build() {
M = euler.size();
int K = 1; while ((1<<K) <= M) K++;
sp.assign(K, vector<int>(M));
for (int i = 0; i < M; i++) sp[0][i] = i;
for (int k = 1; (1<<k) <= M; k++)
for (int i = 0; i + (1<<k) <= M; i++) {
int l = sp[k-1][i], r = sp[k-1][i + (1<<(k-1))];
sp[k][i] = (depthE[l] < depthE[r]) ? l : r;
}
}
int lca(int a, int b) {
int l = first_[a], r = first_[b];
if (l > r) swap(l, r);
int k = 31 - __builtin_clz(r - l + 1);
int x = sp[k][l], y = sp[k][r - (1<<k) + 1];
int idx = (depthE[x] < depthE[y]) ? x : y;
return euler[idx];
}
Сложность: построение O(V log V), запрос O(1). Длина Эйлерова массива = 2V−1. Память O(V log V).
Когда выбирать этот метод против binary lifting. O(1)-на-запрос выигрывает, если запросов очень много (10^6–10^7) и важна константа времени ответа. Binary lifting проще и даёт бонусом k-го предка и подъёмы по пути, что часто нужно в задачах.
Грабля: для разреженной таблицы по индексам храните именно индекс минимума (как выше), а не саму глубину — иначе не восстановите вершину euler[idx]. И обход должен пушить вершину после возврата из каждого ребёнка, иначе first_ и покрытие отрезка собьются (длина массива должна получиться ровно 2V−1).