Preprocessing: Build the Euler tour with first[v] and tourDepth arrays. Then build a sparse table on tourDepth. Query: For lca(u, v), let l = first[u] and r = first[v]. If l > r, swap them. Query the sparse table for the index with minimum depth in . That index points to the LCA node. This combines two effective techniques: Euler tour converts the tree to an array, and sparse table answers range queries in time.
The result: preprocessing, per query. This is a practical online LCA algorithm for static trees. Farach-Colton and Bender's method achieves preprocessing with queries, but this sparse table approach is simpler to implement.
This runs in time per query and uses space.