Here's how it works:

I'll provide 2 solutions:

1. $O(\log{n}\log{\log{n}})$ space and $O(\log{\log{n}})$ query.
2. $O(\log{n}\log{\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 on $\log{n}$ local minimums (powers of 2 technique, but only on $\log{n}$ representatives). Originally, this takes $n\log{n}$ space, but in our case we have only $\log{n}$ representatives so it'll cost $O(\log{n}\log{\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 on $\log{n}$ local minimums (powers of 2 technique, but only on $\log{n}$ representatives). Originally, this takes $n\log{n}$ space, but in our case we have only $\log{n}$ representatives so it'll cost $O(\log{n}\log{\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 in a y-fast 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).