RMQ with $O(\sqrt{n})$ space? I'm asked to design an RMQ data structure (Range Minimum Query: return index of $min$ in a range $[i,j]$) for an array that has $&lt;=\log(n)$ local minimums (a local minimum is an index $i$ such that $A[i-1]&gt;A[i]&lt;A[i+1]$).

There are 2 restrictions:


Only $O(\sqrt{n})$ additional space (rather than $O(n)$ which is used for the regular RMQ d.s. Also see here)
Only a constant number of entry readings from the original array while answering a query


I thought of a solution that uses $\log(n)\log\log(n)$ space. Which is $&lt; \sqrt{n}$ for $n&gt;1165$ according to wolframalpha. (as @jbapple said, $\log(n)\log\log(n)=O(\sqrt{n})$ so that's fine)

edit: i found an error in the solution: in part 3, each item needs to know which section it belongs to (or at least the closest local min to it) - that's already $O(n)$ additional space.

However, i won't delete it so maybe it can be modified to a correct solution

My solution:

Find all local minimums and save pointers to them in $O(n)$ time, $O(\log n)$ space $(&lt;\sqrt{n}\space)$ .

Apply regular RMQ on $\log(n)$ local minimums (powers of $2$ technique - section 3.3 page 5 in this paper). This takes $n\log(n)$ space, but $n$ in my case is $\log(n)$ (number of "representatives"), so it'll cost $\log(n)\log\log(n)$ space only. This is for part 3 - see ahead.

Answering a query:

There are 3 types of queries:


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

This is easily solved in $O(1)$ since it's either the leftmost or rightmost entry
Range between 2 local mins (not including):

Also easy (same method)
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).


Sections of "local min to local min" can be solved in $O(1)$ using the regular RMQ we built above.
Regarding the other 2 sections, for each of them we can determine the min in $O(1)$ (must be either leftmost or rightmost item).
Finally we're left with exactly 3 numbers. Get their min in $O(1)$
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).