The Relationship Between LCA and RMQ
===================================

In the following section, we examine another problem that appears unrelated at first glance but has a close connection to the LCA problem. We then present a solution with time complexity :math:`O(n \lg n + q)` using this problem, which performs better than previous methods when the number of queries is large relative to the number of tree vertices.

In this problem, you are first given an array of size *n*, followed by *q* queries. In each query, you are given the two endpoints of a range and asked to find the **minimum element** within this range. Using the **segment tree** discussed earlier, you can solve this problem in :math:`O(n + q \lg n)`. If the problem instead required the **sum of elements** in the range, it could easily be solved in :math:`O(n + q)`. This problem is called **RMQ** (Range Minimum Query).

Converting RMQ to LCA
---------------------
Here, we build a Cartesian tree from the input array. A Cartesian tree is a binary tree 
where each element of the array corresponds to a node in the tree. The node corresponding 
to the minimum element of the array is placed at the root. The left subtree is equivalent 
to the Cartesian tree of the subarray from the beginning to the minimum element, and the 
right subtree is equivalent to the Cartesian tree of the subarray from the minimum element 
to the end. In the figure below, you can see a Cartesian tree.

.. figure:: /_static/dot/Cartesian_Tree.svg
 :width: 40%
 :align: center
 :alt: An example image of a Cartesian tree

Using the fact that the lowest common ancestor lies within the interval between these two nodes, 
prove that to find the minimum in the interval, one can find the LCA in the Cartesian tree. 
Subsequently, by presenting an :math:`O(n)` method for constructing the Cartesian tree, 
we demonstrate that if there exists a solution for RMQ, there will also exist a solution 
with the same complexity for LCA.

Building a Cartesian Tree in Linear Time
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
A Cartesian tree can be constructed using a stack. The stack maintains vertices whose parent is not yet determined, ordered both by value and position. Starting with an empty stack, we traverse the array. For each element, we pop elements from the stack as long as they are larger than the current element. The parent of all popped vertices is now determined, as no preceding element in the array can be their parent. The parent of each popped vertex is the previous vertex in the stack, and the parent of the last popped vertex is the current element. We then push the current element into the stack and proceed. In the end, we obtain a forest whose roots remain in the stack. These roots are sequentially linked as parent-child pairs (since no new elements remain), with the last element in the stack becoming the tree's root (which is also the array's minimum element).

.. _converting-lca-to-rmq:

Converting LCA to RMQ
---------------------
We perform a 
DFS
traversal on the tree. Upon entering each vertex, we add it to the array and 
set its value equal to its height. When exiting each vertex, we also add its parent 
to the array in the same way. Each vertex has a corresponding number of entries in 
the array equal to its number of children plus one. To find the lowest common ancestor, 
we simply need to compute the minimum element between the corresponding entries 
of the two target vertices in the array and determine which vertex it corresponds to. 
The proof of this is left to the reader. Therefore, if a solution exists for either 
the LCA or RMQ problem, a solution with the same complexity exists for the other.

Solving RMQ with Sparse Table
--------------------------------
The sparse table is a special type of dynamic programming where the second dimension has a logarithmic size relative to the first. This table is used in various problems, and here we use it to solve this problem.

Let :math:`dp_{i,j}` be the minimum element in the interval :math:`[i,i+2^j)`. If we have this dp, we can answer queries in :math:`O(1)`. Specifically, we find a **j** such that the length of the target interval lies between :math:`2^j` and :math:`2^{j+1}`. The answer to the query will then be:

.. math:: min(dp_{l,j},dp_{r-2^j,j})

Computing this table is also feasible in :math:`O(n \lg n)`. Starting from **j=0**, we proceed up to the logarithm of the array's length. Each **j** is derived from the previous **j** using:

.. math:: dp_{i,j}=min(dp_{i,j-1},dp_{i+2^{j-1},j-1})

Thus, for **RMQ** and **LCA**, we obtain an algorithm with time complexity :math:`O(n \lg n + q)`. When **n** is smaller than **q**, this performs better than the previous :math:`O(n + q \lg n)` algorithm.