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 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.