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 tourdepth[]: depth of each node in tourfirst[]: first occurrence of each node in tour For LCA of nodes and :
Find first occurrences: ,
Query for minimum depth in range
The node at that minimum depth position is the LCA This reduces LCA to RMQ, giving LCA queries after preprocessing.