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 $A[i]

-
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 $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 $(

• 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 ($$ 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$ 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&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).

StackExchange Computer Science Q#29542, answer score: 2