§ Cartesian Trees

Cartesian trees construct a tree T=C(A)T = C(A) given an array AA, such that range minimum query (RMQ) on the array AA is equivalent to the lowest common ancestor (LCA) of the nodes of the tree TT. Note that the tree looks like a min-heap. To see the connection to LCA, if we want to find the range minimum in the range containing the elements [12, 10, 20, 15, 18] of the array, the minimum is 10, which is indeed the lowest common ancestor of the nodes of 12 and 18 in the tree.

§ Building a Cartesian tree in linear time:

§ Converting LCA to RMQ

We can go the other way, and convert an LCA problem into a RMQ problem. We perform an inorder traversal of the nodes, scribbling down the depth of the node (Link to lecture at 15:30). We ask for the argmin version of RMQ, that gives us the index of the node with the lowest depth. This gives us the index of where the node lives.

§ Universe reduction in RMQ

We can have an arbitrary ordered universe, on which we want to perform RMQ. We can convert this to LCA by using a cartesian tree, and then convert to a "clean" RMQ (by using the LCA -> RMQ using depth conversion). This now will give us way faster operations (since we now have integers).

§ +-1 RMQ:

We want the differences between nodes to have a difference of only +-1. We had a much wider gap. Here, we perform an Euler tour (walk the tree DFS search order), and sribble down every vertex we visit. To find the LCA, we perform the RMQ on the locations of the first occurence of the node. (I think we don't actually need the first occurence, any occurence will do).

§ References