Due to Micahel bender and martin Colton
Definition. Given a tree (not necessarily balanced) LCA(x,y) means the least common ancestor.
Definition. Given an array RMQ(i,j) means the smallest element that occurs in the array between indices \(i\) and \(j\).
Theorem. Say we write down the nodes and depths of nodes as they occur in a DFS traversal of a tree. then the shalowest node that we encounter on the DFS between two vertices \(x,y\) is their LCA.
beg pf yes end pf
Corollary. Thus, LCA is reduced to RMQ. But actually a very special RMQ: RMQ on an array where adjacent elements differ by \(\pm 1\).
Theorem. we can solve RMQ pretty easily in \(O(n\log n)\) prep, \(O(1)\) query. But \(\pm 1\) RMQ we can do in \(O(n)\) prep, \(O(1)\) query. by four russians.
Theorem. We can reduce general RMQ to LCA, by constructing a cartesian tree thing in linear time.
Definition. cartesian tree thing: root is min element. that splits the array into two parts, left and right. then recursively construct those.
note : if you build one node at a time you can build this in linear time.