RMQ with $O(\sqrt{n})$ space?
Here's how it works:

I'll provide 2 solutions:


$O(\log{n})$ space and $O(\log{\log{n}})$ query.
$O(\log{n})$ space and $O(\log{\log{\log{n}}})$ query.


1) Using binary search on local mins.

Find all local minimums and store them in an array $B$ in their original order - $O(n)$ time, $O(\log{n})$ space ($&lt;O(\sqrt{n})$). Also, let each item remember its original index. Now apply regular $RMQ&lt;O(n),O(1)&gt;$ structure on $\log{n}$ local minimums ($\log{n}$ space.)
To answer a query, each item must know its block’s beginning and ending points. But that would cost $O(n)$ additional space so we can’t afford it. Instead, given an interval $[i,j]$, we binary-search the array $B$ for indices $i$ and $j$ to find the closest index which has a local_min.

Answering a query:

There are 3 types of queries:


Range begins just after a local minimum and ends just after the next one:




First, we need to recognize we’re in this case. Perform a binary search on array $B$ for index $j$ or the smallest index larger than $j$. And symmetrically for $i$. In this case we’ll find exactly $i-1$ and $j$. That indicates the interval covers exactly 1 block. Therefor the answer is either $i$ or $j$ (proof below). Time: $O(\log{\log{n}})$.


Range between 2 local mins (not including):


Same method as above, but this time we’ll find  $i-2$  and  $j+2$ . That means we’re inside a block. The min must be either $i$ or $j$ (proof below) – Check that in $O(1)$. Time: $O(loglogn)$.




Overlapping range:




This always overlaps complete sections of "local min to local min" and exactly 2 small sections from the right and left sides (see picture).
Again, to recognize the case, binary-search for $i,j$ in $B$. Obviously, we’ll find $i$ and $j-1$ . This means $j$ overpasses the end of a block, and i overpasses a beginning of a block. Therefore, the min is: either one of the local minimums at that range, or one of the 2 edges (leftmost or rightmost – i.e $A[i]$ or $A[j]$). Solve query $[i,j-1]$ by RMQ, compare the returned min with $A[i]$ and $A[j]$ in $O(1)$, one of those 3 is the min. Time: $O(\log{\log{n}})$.

2) Using y-fast trie on local mins.

Find all local minimums and store them in a y-fast trie structure (call it $Y$) and let the keys be the original indices - $O(n)$ time, $O(\log{n})$ space. Now apply regular $RMQ&lt;O(n),O(1)&gt;$ structure on $\log{n}$ local minimums ($\log{n}$ space.)
To answer a query, each item must know its block’s beginning and ending points. But that would cost $O(n)$ additional space so we can’t afford it. Instead, given an interval $[i,j]$, we search $Y$ for indices $i$ and $j$ (or their pred and succ) to find the closest index which has a local_min. Search of pred/succ in a y-fast-trie of $n$ elements takes $O(\log{\log{n}})$.

Answering a query:

There are 3 types of queries:


Range begins just after a local minimum and ends just after the next one:




First, we need to recognize we’re in this case. Search for index $j$ or its successor in $Y$. And symmetrically for $i$. In this case we’ll find exactly $i-1$ and $j$. That indicates the interval covers exactly 1 block. Therefor the answer is either $i$ or $j$ (proof below). Time: $O(\log{\log{\log{n}}})$.


Range between 2 local mins (not including):




Same method as above, but this time we’ll find  $i-2$  and  $j+2$ . That means we’re inside a block. The min must be either $i$ or $j$ (proof below) – Check that in $O(1)$. Time: $O(\log{\log{\log{n}}})$.


Overlapping range:




This always overlaps complete sections of "local min to local min" and exactly 2 small sections from the right and left sides (see picture).

Again, to recognize the case, search for $i,j$ in $Y$. Obviously, we’ll find $i$ and $j-1$ . This means $j$ overpasses the end of a block, and $i$ overpasses a beginning of a block. Therefore, the min is: either one of the local minimums at that range, or one of the 2 edges (leftmost or rightmost – i.e $A[i]$ or $A[j]$). Solve query $[i,j-1]$ by RMQ , compare the returned min with $A[i]$ and $A[j]$ in $O(1)$, one of those 3 is the min. Time: $O(\log{\log{\log{n}}})$.

Proof for cases 1&amp;2:

Theorem: in this type of ranges, the min is either the leftmost or rightmost entry.
Proof by contradiction: Suppose the min is somewhere inside the block, and not at the edges.
If it’s the min then it’s smaller than both its left and right neighbors. Thus it’s a local_min by definition. This is a contradiction because we assumed we have a block from a local_min to the next local_min (no local_mins’s in between).