Case 1: if i and j are in different blocks

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.

Case 2: if i and j are in the same block

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.