RMQ with $O(\sqrt{n})$ space?

Question

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 $<=\log(n)$ local minimums (a local minimum is an index $i$ such that $A[i-1]>A[i]<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 $< \sqrt{n}$ for $n>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 $(<\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:

1. 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
2. Range between 2 local mins (not including): Also easy (same method)

3. 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)$

Answer 1

Here's how it works:

I'll provide 2 solutions:

1. $O(\log{n})$ space and $O(\log{\log{n}})$ query.
2. $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 ($<O(\sqrt{n})$). Also, let each item remember its original index. Now apply regular $RMQ<O(n),O(1)>$ 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:

1. 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}})$.

2. 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)$.

3. 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<O(n),O(1)>$ 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:

1. 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}}})$.

2. 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}}})$.

3. 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).