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 the fastest known online LCA algorithm for static trees. No other method beats query time.
This runs in time per query and uses space.