LCA with Sparse Table

Lowest Common Ancestor you can reduce to RMQ using Euler tour. The Euler tour visits each node when entering and after visiting each child. Record:

• euler[]: sequence of nodes in tour
• depth[]: depth of each node in tour
• first[]: first occurrence of each node in tour For LCA of nodes $u$ and $v$:

$1.$ Find first occurrences: $i = \text{first}[u]$, $j = \text{first}[v]$

$2.$ Query for minimum depth in range $[\min(i,j), \max(i,j)]$

$3.$ The node at that minimum depth position is the LCA This reduces LCA to RMQ, giving $O(1)$ LCA queries after $O(n \log n)$ preprocessing.