Lowest Common Ancestor with a Sparse Table
The lowest common ancestor, or LCA, of vertices and is their common ancestor with the greatest depth. A vertex is considered its own ancestor.
During DFS, record each vertex when entering it. After returning from a child, record the parent again.
This sequence is called an Euler tour.
For every vertex , store:
The tour has entries: the root is recorded once, and each of the edges adds one entry when going down and one when returning.
Consider the segment between the first occurrences of and . Their LCA is the vertex with minimum depth in this segment.
Let .
If one of the query vertices is , the segment starts with . Otherwise, and belong to different child subtrees of , so DFS must return to between their first visits. In either case, appears in the segment.
During this part of DFS, we stay inside 's subtree: DFS cannot finish this subtree before visiting both vertices. Every vertex in the segment therefore has depth at least . The only vertex in this subtree with depth is itself.
So finding the vertex with minimum depth gives the LCA.
Build a sparse table over the Euler tour. Each entry stores the vertex with minimum depth in the segment of length starting at position .
For a query, let
and choose
Use the two segments of length : one starting at , and one ending at . Compare the depths of the vertices stored in
and return the vertex with the smaller depth.
The two segments cover , and their overlap does not affect the minimum.
The Euler tour has entries. Building the tour takes time, and building the sparse table takes time. Each LCA query takes time.
The sparse table uses entries. The global arrays in the implementation reserve space for the maximum supported tree size. The tree and root stay fixed between queries.
#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
const int K = 20;
vector<int> g[N];
int d[N], pos[N], lg[2 * N];
int t[K][2 * N], m;
int best(int u, int v) {
return d[u] < d[v] ? u : v;
}
void dfs(int v, int p) {
pos[v] = m;
t[0][m++] = v;
for (int u : g[v]) {
if (u == p) continue;
d[u] = d[v] + 1;
dfs(u, v);
t[0][m++] = v;
}
}
void build(int root = 1) {
m = 0;
d[root] = 0;
dfs(root, 0);
for (int i = 2; i <= m; i++) {
lg[i] = lg[i / 2] + 1;
}
for (int k = 1; k <= lg[m]; k++) {
for (int i = 0; i + (1 << k) <= m; i++) {
t[k][i] = best(t[k - 1][i],
t[k - 1][i + (1 << (k - 1))]);
}
}
}
int lca(int u, int v) {
int l = pos[u], r = pos[v];
if (l > r) swap(l, r);
int k = lg[r - l + 1];
return best(t[k][l], t[k][r - (1 << k) + 1]);
}