Range Min Query

Problem

Definition (Range Min Query). Let $a_1, \ldots, a_n \in \mathbb{R}$. Given $\ell, r \in [n]$, $\ell \le r$, return $\min \{ a_\ell, \ldots, a_r \}$.

Basic Solutions

A data structure for the Range Min Query (RMQ) has complexity $\left< p(n), q(n) \right>$ if it has pre-processing and query-answering time $p(n)$ and $q(n)$ on input instance of size $n$, respectively.

$\mathcal{A}_1$ Precompute-None

Scan $a_\ell, \ldots, a_r$ to find the min.

• This is an $\left< 0, O(n) \right>$ solution.

$\mathcal{A}_2$ Complete Binary Tree

Construct a complete binary tree with $a_1, \ldots, a_n$ being the leaf nodes. Each internal node of the tree is augmented with the minimum value of its subtree.

• This is an $\left< O(n), O(\log n) \right>$ solution.

$\mathcal{A}_3$ Precompute-All

Create a $n \times n$ table $M$. For each $\ell, r \in [n]$, $\ell \le r$, the $(\ell, r)$-th entry records $\min \{ a_\ell, \ldots, a_r \}$.

• This is an $\left< O(n^2), O(1) \right>$ solution.

• $p(n) = O(n^2)$.

  • Dynamic Programming.
  • $\forall \ell, r \in [n], \ell \le r$,$$M[\ell, r] = \begin{cases} a_\ell & \ell = r, \\ \min \{ M[\ell, r - 1], M[\ell + 1, r] \}, & \ell < r. \end{cases}$$

• $q(n) = O(1)$.

$\mathcal{A}_4$ Sparse Table

Create a $n \times \lfloor \log n \rfloor$ table $M$. For each $\ell \in [n], k \in \big[ \lfloor \log n \rfloor \big]$, $r \doteq \ell + \big( 2^k - 1 \big) \le n$, the $(\ell, k)$-th entry records $\min \{ a_\ell, \ldots, a_{\ell + 2^k - 1} \}$.

• This is an $\left< O(n \log n), O(1) \right>$ solution.

• $p(n) = O(n \log n)$.

  • Dynamic Programming.
  • For each $\ell \in [n], k \in \big[ \lfloor \log n \rfloor \big]$, $r \doteq \ell + \big( 2^k - 1 \big) \le n$, let$$M[\ell, k] = \begin{cases} \min \{ a_\ell, a_{\ell + 1} \} & k = 1, \\ \min \{ M[\ell, \ell + 2^{k - 1} - 1], M[r - 2^{k - 1} + 1, r] \}, & \ell < r. \end{cases}$$

• $q(n) = O(1)$.

Divide and Conquer

Preprocessing

1. Pick $s \in \mathbb{N}_+$, and let $m = n / s$.

2. Partition $a_1, \ldots, a_n$ into $m$ blocks $B_1, \ldots B_m$, such that $B_1$ contains the first $s$ elements, $B_2$ contains the next $s$ elements, and so on. In general,

3. Denote $b_1, \ldots, b_m$ be the minimum element in $B_1, \ldots B_m$, respectively.

Query

4. Given $\ell, r \in [n]$, $\ell \le r$, consider

   • $C_1$ be the collection of indexes of the blocks $B_i \subset \{ a_\ell, \ldots, a_r \}$:

     $$C_1 \doteq \{ i \in [m] : B_i \subset \{ a_\ell, \ldots, a_r \} \}$$

     If $C_1 \neq \emptyset$, let $\ell' = \min_{i \in C_1} i$ and $r' = \max_{i \in C_1} i$.

   • $C_2$ be the collection of indexes of the blocks $B_i$ such that $B_i \nsubseteq \{ a_\ell, \ldots, a_r \}$ and $B_i \cap \{ a_\ell, \ldots, a_r \} \neq \emptyset$

     $$C_2 \doteq \{ i \in [m] : B_i \cap \{ a_\ell, \ldots, a_r \} \neq \emptyset \wedge B_i \nsubseteq \{ a_\ell, \ldots, a_r \} \}.$$

     It must be that $|C_2| \le 2$.

5. To return $\min \{ a_\ell, \ldots, a_r \}$, return the minimum of

   • $\min_{i \in C_1} b_i$, if $C_1 \neq \emptyset$.
   • $\min_{i \in C_2} \min \big( B_i \cap \{ a_\ell, \ldots, a_r \}\big)$.

   Note that

   • The first one is a range-min query on $b_1, \ldots, b_m$.
   • The second one consists of range-min queries on the blocks $B_i$ for $i \in C_2$

Approach One

1. Suppose we invoke an algorithm $A_{up}$ to answer the range-min query on $b_1, \ldots, b_m$, with complexity $\left< p_1(m), q_1(m) \right>$.

2. Suppose we invoke an algorithm $A_{down}$ to answer the range-min query range-min queries on the blocks $B_i$ for $i \in C_2$, with complexity $\left< p_2(s), q_2(s) \right>$.

3. Since the set $C_2$ depends on the range min query, to answer arbitrary range min query, we need to run the pre-processing of $A_{down}$ on each block $B_i, i \in [m]$.

This approach has complexity

Instantiation

$\mathcal{A}_5$ Two-Level Precompute-None

Choose Precompute-None $\mathcal{A}_1$ for both $A_{up}$ and $A_{down}$.

• Total preprocessing time: $O \big( n \big)$.
• Total query time: $O \big( m + s \big) = O \big( \sqrt{n} \big)$, if $m = s = \sqrt{n}$.

Hence, it has complexity $\left< O \big( n \big), O \big( \sqrt{n} \big) \right>$.

$\mathcal{A}_6$ Two-Level Binary Tree

This is just a complete binary tree over $a_1, \ldots, a_n$. Therefore,

• Total preprocessing time: $O \big( n \big)$.

• Total query time: $O \big( \log n \big)$.

Hence, it has complexity $\left< O \big( n \big), O \big( \log n \big) \right>$.

$\mathcal{A}_7$ Two-Level Sparse Table

We don't investigate Precompute-All, as the sparse table is always better.

Choose sparse table $\mathcal{A}_3$ for both $A_{up}$ and $A_{down}$.

• Total preprocessing time: $O \big( m \log m + m \cdot s \log s \big)$.
  Since $m \cdot s = n$, we have

  $$O \Big( m \log m + m \cdot s \log s \Big) = O \Big( \frac{n}{s} \log \frac{n}{s} + n \log s \Big),$$

  which is minimized when

  $$\begin{aligned} \frac{n}{s} \log \frac{n}{s} = n \log s &\iff \log n - \log s = s \log s \\ &\iff \log n = \Theta (s \log s ) \\ &\iff \log \log n = \Theta (\log s). \end{aligned}$$

  Therefore, the pre-processing time is reduced to

  $$O \Big( n \log \log n \Big).$$

• Total query time: $O \big( 1 + 1 \big) = O \big( 1 \big)$.

Hence, it has complexity $\left< O \big( n \log \log n \big), O \big( 1 \big) \right>$.

Remark: Personally I suspect this approach is fast in practice. Since $A_{down}$ involves a linear scan of at most two blocks with size $O(\log n)$, and linear scan is cache-friendly.

Remark: If we apply two level $\mathcal{A}_7$, then the preprocessing time is

Choosing $s = \log \log s$ minimized this to

Further, the query time remains $O(1)$.

$\mathcal{A}_8$ Hybrid-Sparse Table and Precompute-None

Choose sparse table $\mathcal{A}_3$ for $A_{up}$ and Precompute-None $\mathcal{A}_1$ for $A_{down}$.

• Total preprocessing time: $O \big( (n / s) \log (n / s) \big)$.

• Total query time: $O \big( 1 + s \big)$.

If we choose $s = \log n$, then

• Total preprocessing time: $O \big( n \big)$.

• Total query time: $O \big( \log n \big)$.

Hence, it has complexity $\left< O \big( n \big), O \big( \log n \big) \right>$.

$\mathcal{A}_9$ Hybrid-Sparse Table and Binary Tree

Choose sparse table $\mathcal{A}_3$ for $A_{up}$ and complete binary tree $\mathcal{A}_2$ for $A_{down}$.

• Total preprocessing time: $O \big( (n / s) \log (n / s) + (n / s)\cdot s \big)$.

• Total query time: $O \big( 1 + \log s \big)$.

If we choose $s = \log n$, then

• Total preprocessing time: $O \big( n \big)$.

• Total query time: $O \big( \log \log n \big)$.

Hence, it has complexity $\left< O \big( n \big), O \big( \log \log n \big) \right>$.

Remark: If we apply two level $\mathcal{A}_9$, then the preprocessing time is

Further, the query time is

Unfortunately, this is still $\log \log n$.

Approach Two

Can we achieve $\left< O \big( n \big), O \big( 1 \big) \right>$ under approach one? Recall that approach one has complexity

Suppose we want to achieve preprocessing time $O(n)$ and query time $O(1)$, then $p_2(s)$ and $q_2(s)$ needs to satisfy that $p_2(s) = s$ and $q_2(s) = 1$. But this is exactly the property we want to achieve!

It seems to be impossible to achieve the desired complexity under the divide and conquer framework.

The key is to observe that the following are two different problems.

1. Finding a RMQ algorithm with complexity $\left< O(n), O(1) \right>$.
2. Finding an algorithm that preprocess the all block $B_i$ in $O(n)$ time, such that the range-min query on each $B_i$ can be answered in $O(1)$ time.

For the divide-and-conquer framework to work to achieve complexity $\left< O(n), O(1) \right>$, it suffices to find an algorithm for the second problem.

Theorem. There exists some $s \in \Theta(\log n)$, such that we can find an algorithm that preprocess the all block $B_i$ in $O(n)$ time, such that the range-min query on each $B_i$ can be answered in $O(1)$ time.

Denote such an algorithm as $\mathcal{A}^*$. Since $s \in \Theta(\log n)$, choosing sparse table algorithm $\mathcal{A}_3$ to answer the range-min query on $b_1, \ldots, b_m$ incurs additional preprocessing time $O( n / s \cdot \log (n / s) ) = O(n)$. Further, answering a query requires only $O(1)$ time.

It is left to show the construction of $\mathcal{A}^*$.

Block Type

W.L.O.G., consider the first block $B_1 = \{ a_{ 1 }, \ldots, a_{ s} \}$ be a block of $s$ elements. We can construct a binary tree over the elements, such that it satisfies

1. Min Heap Property: each node of the tree is the smallest one in the subtree rooted at this node.
2. The in-order traversal of the tree gives the array $B_1$.

Such a binary tree is called a Cartesian Tree and the type of the block.

On the other hand, suppose we are given a Cartesian Tree tree constructed on $B_1$, and suppose that the value of each node of the tree is hidden. Hence, we only know the topology or shape of the binary tree. For all $1 \le \ell \le r \le s$, we can still return the index of the minimum element among $a_\ell, \ldots, a_s$, purely based on the topology of the binary tree.

In this sense, the answers to the RMQ on $B_1$ is entirely determined by its corresponding Cartesian Tree.

Enumeration

This motivates the following strategy.

1. Enumerate all possible Cartesian Trees.

2. For each Cartesian Tree, invoke the sparse table algorithm $\mathcal{A}_3$ algorithm on this tree, so that all possible range min query for this tree can be answer in $O(1)$ time.

3. For each block $B_i, i \in [m]$, determine its Cartesian Trees. To answer a RMQ on $B_i$, access the pre-computed result on its corresponding Cartesian Trees.

Fact. The number of distinct Cartesian Trees with size $s$ is given by

$$\frac{1}{1 + s}\binom{2s}{s}.$$

Therefore, enumerating the Cartesian Trees, and constructing sparse tables on them for RMQ, take time and space

Choosing $s = \big( 0.5 \cdot \log n \big)$ gives $\Theta( n \cdot \big( \log \log n \big) / \sqrt{\log n}) \subset O(n)$.

Determining the Block Type

In this section, we show how to construct the corresponding Cartesian Tree given the block $B_1$, and to create a unique identifier $\in O(n)$ for the Cartesian Tree.

We illustrate the idea with an example. In this example, $B_1 = (2, 4, 3, 1)$. We will construct the Cartesian Tree, by including the elements from $B_1$ one by one. Further, we maintain a stack and a stack operation sequence, both of which are initially empty. The stack keeps elements from the right spine of the tree, and the stack operation sequence records the "in stack" and "out stack" operations as we include more elements from $B_1$ into the tree.

We first include the element $2$ into the tree. Since the tree consists of only one node, it is the root of the tree. It is also the only node in the right spine of the tree, so we put $2$ into the stack, and append $1$ to the stack operation sequence, to record the in-stack operation.

Next we include the element $4$ into the tree. Since the tree satisfies min-heap property, $4$ must be the child of $2$. Since the in-order traversal of the tree gives the array $2, 4$, the node $4$ must be the right child of $2$. We put $4$ into the stack, and append $1$ to the stack operation sequence, to record the in-stack operation.

We want to include the element $3$ into the existing tree. Since after inclusion, the in-order traversal of the tree gives the array $2, 4, 3$, the node $3$ must be in the right spine of the tree. Indeed, this is a general principle for adding a new element into the tree.

Lemma (In the Right Spine). For each $j \in [s]$, let $T_j$ be the Cartesian tree constructed on $a_1, \ldots, a_j$. Then $a_j$ be must in the right spine of $T_j$.

Proof.

1. If $a_j$ has right-child in $T_j$, then it is not the last element visited by the in-order traversal of $T_j$.
2. If $a_j$ has a parent node in $T_j$ and is the left-child of its parent, then it is not the last element visited by the in-order traversal of $T_j$.

$\square$

In this case, the right spine consists of $2$ and $4$. We compare $3$ with $4$. As it is smaller than $4$, we pop $4$ out of the stack. We compare $3$ with $2$. As it is larger than $2$, we put $3$ into the stack. We include $3$ as the right-child of $2$, and set $4$ as the left child of $3$. We see that after these operations, the stack still contains the nodes in the right spine of the tree. Further, the min-heap property of the tree is maintained. We append $01$ to the stack operation sequence, to record the out-stack and in-stack operations performed.

We now formally states the rules for adding an element to the right spine.

Incremental Construction Rule. For each $1 \le j < s$, let $T_j$ be the Cartesian tree constructed on $a_1, \ldots, a_j$, and suppose that $a_1' \le a_2' \ldots \le a_k'$ are the elements in the right spine of $T_j$. Then $a_{j + 1}$ is added to $T_j$ as follows:

1. If $a_{j + 1} < a_1'$, then set $a_1'$ as the left child of $a_{j + 1}$.

2. If $a_{j + 1} > a_k'$, then set $a_{j + 1}$ as the right child of $a_k'$.

3. Otherwise, there exists $1 \le i < k$, such that $a_i' \le a_{j + 1} < a_{i + 1}'$. Replace $a_{i + 1}'$ by $a_{j + 1}$ as the right child of $a_i'$, and set $a_{i + 1}'$ as the left child of $a_{j + 1}$.

It is easy to verify that after the construction

1. $a_{j + 1}$ is in the right spine of the tree.
2. The min-heap property is maintained.

We want to include the element $1$ into the existing tree. Since after inclusion, the in-order traversal of the tree gives the array $2, 4, 3, 1$, the node $1$ must be in the right spine of the tree. In this case, the right spine consists of $2$ and $3$. As $1$ is smaller than $2$, we pop $3$ and $2$ out of the stack, put $1$ into the stack, and set $2$ as the left child of $1$. We append $001$ to the stack operation sequence, to record the stack operations performed.

Finally, we pop $1$ out of the stack, and append $0$ to the stack operation sequence, to record the stack operation performed. We perform this operation, so that whatever sequence of $a_1, \ldots, a_s$, the stack operation sequence corresponding to the Cartesian Tree construction procedure stated as above has length $2s$.

The construction also reveal an interesting fact: each Cartesian Tree with $s$ node corresponding a $0$-$1$ sequence with length $2s$, such that each prefix of the sequence contains no less $1$'s than $0$'s.

We know that

which gives a construct proof of the number of binary trees with $s$ nodes.

Reference

[1] Stanford, CS 166, Range Minimum Queries