Lowest common ancestor

Reduction of LCA into RMQ started by walking the tree. When walking the tree, the order of the label and the depth of the node visited is recorded. Then a LCA question can be answered by answering a RMQ question which the input of a RMQ problem is the indices of two child nodes in the list of visited nodes.

An example shown how RMQ is reduced into LCA.

Therefore, LCA can be solved by solving RMQ.

Despite that there exists a constant time and linear space solution for general RMQ, but a simplified solution can be applied that make uses of LCA’s properties. This simplified solution can only be used for RMQ reduced from LCA.

Similar to the solution mentioned above, we divide the sequence into each block ${\displaystyle B_{i}}$, where each block ${\displaystyle B_{i}}$ has size of ${\displaystyle b={1 \over 2}\log n}$.

An illustartion showing a RMQ problem is divided into blocks that each has size = b

By splitting the sequence into blocks, the ${\displaystyle RMQ(i,j)}$ query can be solved by solving two different cases:

To answer the ${\displaystyle RMQ(i,j)}$ query in case one, there are 3 groups of variables precomputed to help reduce query time.

First, the minimum element with the smallest index in each block ${\displaystyle B_{i}}$ is precomputed and denoted as ${\displaystyle y_{i}}$. A set of ${\displaystyle y_{i}}$ takes ${\displaystyle O(n/b)}$ space.

Second, given the set of ${\displaystyle y_{i}}$, the RMQ query for this set is precomputed using the solution with constant time and linearithmic space. There are ${\displaystyle n/b}$ blocks, so the lookup table in that solution takes ${\displaystyle O({n \over b}\log {n \over b})}$ space. Because ${\displaystyle b={1 \over 2}\log n}$, ${\displaystyle O({n \over b}\log {n \over b})}$ = ${\displaystyle O(n)}$ space. Hence, the precomputed RMQ query using the solution with constant time and linearithmic space on these blocks only take ${\displaystyle O(n)}$ space.

Third, in each block ${\displaystyle B_{i}}$, let ${\displaystyle k_{i}}$ be an index in ${\displaystyle B_{i}}$ such that ${\displaystyle 0\leq ki<b}$. For all ${\displaystyle k_{i}}$ from ${\displaystyle 0}$ until ${\displaystyle b}$, block ${\displaystyle B_{i}}$ is divided into two intervals ${\displaystyle [0,k_{i})}$ and ${\displaystyle [k_{i},b)}$. Then the minimum element with the smallest index for intervals in ${\displaystyle [0,k_{i})}$ and ${\displaystyle [k_{i},b)}$ in each block ${\displaystyle B_{i}}$ is precomputed. Such minimum elements are called as prefix min for the interval in ${\displaystyle [0,k_{i})}$ and suffix min for the interval in ${\displaystyle [k_{i},b)}$. Each iteration of ${\displaystyle k_{i}}$ computes a pair of prefix min and suffix min. Hence, the total number of prefix mins and suffix mins in a block ${\displaystyle B_{i}}$ is ${\displaystyle 2b}$. Since there are ${\displaystyle n/b}$ blocks, in total, all prefix min and suffix min arrays take ${\displaystyle O(2b\cdot {n \over b})}$ which is ${\displaystyle O(n)}$ spaces.

In total, it takes ${\displaystyle O(n)}$ space to store all 3 groups of precomputed variables mentioned above.

Therefore, answering the ${\displaystyle RMQ(i,j)}$ query in case 1 is simply tasking the minimum of the following three questions:

Let ${\displaystyle B_{i}}$ be the block that contains the element at index ${\displaystyle i}$, and ${\displaystyle B_{j}}$ for index ${\displaystyle j}$.

1. The suffix min in ${\displaystyle [i\mod b,b)}$ in the block${\displaystyle B_{i}}$
2. Answering the RMQ query on a subset of ${\displaystyle y}$s from blocks ${\displaystyle \{B_{i+1}...B_{j-1}\}}$using the solution with constant time and linearithmic space
3. The prefix min in ${\displaystyle [0,j\mod b)}$ in the block ${\displaystyle B_{j}}$

All 3 questions can be answered in constant time. Hence, case 1 can be answered in linear space and constant time.

The sequence of RMQ that reduced from LCA has one property that a normal RMQ doesn’t have. The next element is always +1 or -1 from the current element. For example:

An illustration showing how the example RMQ is encoded as a bitstring

Therefore, each block ${\displaystyle B_{i}}$ can be encoded as a bitstring with 0 represents the current depth -1, and 1 represent the current depth +1. This transformation turns a block ${\displaystyle B_{i}}$into a bitstring of size ${\displaystyle b-1}$. A bitstring of size ${\displaystyle b-1}$ has ${\displaystyle 2^{b-1}}$ possible bitstrings. Since ${\displaystyle b={1 \over 2}\log n}$, so ${\displaystyle 2^{b-1}\leq 2^{b}=2^{{1 \over 2}\log n}=n^{1 \over 2}={\sqrt {n}}}$.

Hence, ${\displaystyle B_{i}}$ is always one of the ${\displaystyle {\sqrt {n}}}$ possible bitstring with size of ${\displaystyle b-1}$.

Then, for each possible bitstrings, we apply the naïve quadratic space constant time solution. This will take up ${\displaystyle {\sqrt {n}}\cdot b^{2}}$ spaces, which is ${\displaystyle O({\sqrt {n}}\cdot (\log n)^{2})\leq O({\sqrt {n}}\cdot {\sqrt {n}})=O(n)}$.

Therefore, answering the ${\displaystyle RMQ(i,j)}$ query in case 2 is simply finding the corresponding block (in which is a bitstring) and perform a table lookup for that bitstring. Hence, case 2 can be solved using linear space with constant searching time.