<p>The <em>min-gap</em> of an array $A[1..n]$ of $n \ge 2$ elements is defined as $\min_{1 \le i &lt; j \le n}{|A_i - A_j|}$. Now, I am considering a query version of it. Given $A$, a <em>query</em> receives two integers $l$ and $r$, where $1 \le l &lt; r \le n$, and outputs the min-gap of the subarray $A[l..r]$.</p>

<p>We are allowed to preprocess some data structure and use it to answer each query efficiently. Specifically, let $S(n)$ be the extra space needed for preprocessing, and let $Q(n)$ be the query time. Then,</p>

<ol>
<li>Is there an exact solution with $S(n) = O(n)$ and $Q(n) = \text{polylog } n$?</li>
<li>If not, is there an exact solution with $S(n) = O(n)$ and $Q(n) = O(n^c)$, where $0 &lt; c &lt; 0.5$?</li>
<li>If not, is there any approximation solution that achieves the bounds mentioned above?</li>
</ol>

CC BY-SA 3.0
2016-10-07T00:59:11.980Z
Do you really mean to exclude solutions with $S(n) = O(n \lg n)$ and $Q(n) = \text{polylog}(n)$, or would they also be of interest?  What's the best solution you know so far?
D.W.
CC BY-SA 3.0
2016-10-07T01:39:56.383Z
@D.W., we currently have an exact solution with $S(n) = O(n \log n)$ and $Q(n) = \text{polylog}(n)$ via some reduction and are looking for the existence of linear-space solutions. But, we are also interested in your ideas if you are available to share.
Blue Bear
CC BY-SA 3.0
2016-10-07T12:09:33.750Z
There is also a solution with $S(n) = O(n)$ and $Q(n) = O(\sqrt{n} \log n)$ amortized with Mo's algorithm (http://codeforces.com/blog/entry/7383). Here $c \geq 0.5$ and thus you might have known of this solution, but it may be worth sharing anyway.
Ivan Smirnov
CC BY-SA 3.0
2016-10-08T15:37:39.573Z
@IvanSmirnov, yes, we are aware of that technique. Thanks for sharing anyway. :)
Blue Bear
CC BY-SA 4.0
2020-01-05T11:13:59.070Z
A 2-approximation in $Q(n) = \log{a} \log{n}$ is possible, but this isn't $\mathcal{O}(n^c)$.
Antti Röyskö
<ds.data-structures><query-complexity><space-complexity>
Range min-gap query
Blue Bear
# Range min-gap query

(Asked by: username_0 on 2016-10-05)

The *min-gap* of an array $A[1..n]$ of $n \ge 2$ elements is defined as $\min\_{1 \le i < j \le n}{|A\_i - A\_j|}$. Now, I am considering a query version of it. Given $A$, a *query* receives two integers $l$ and $r$, where $1 \le l < r \le n$, and outputs the min-gap of the subarray $A[l..r]$.

We are allowed to preprocess some data structure and use it to answer each query efficiently. Specifically, let $S(n)$ be the extra space needed for preprocessing, and let $Q(n)$ be the query time. Then,

1. Is there an exact solution with $S(n) = O(n)$ and $Q(n) = \text{polylog } n$?
2. If not, is there an exact solution with $S(n) = O(n)$ and $Q(n) = O(n^c)$, where $0 < c < 0.5$?
3. If not, is there any approximation solution that achieves the bounds mentioned above?

**Tags:** ds.data-structures, query-complexity, space-complexity
> **Comments:**
> **username_1**: Do you really mean to exclude solutions with $S(n) = O(n \lg n)$ and $Q(n) = \text{polylog}(n)$, or would they also be of interest?  What's the best solution you know so far?  
> **username_0**: @D.W., we currently have an exact solution with $S(n) = O(n \log n)$ and $Q(n) = \text{polylog}(n)$ via some reduction and are looking for the existence of linear-space solutions. But, we are also interested in your ideas if you are available to share.  
> **username_2**: There is also a solution with $S(n) = O(n)$ and $Q(n) = O(\sqrt{n} \log n)$ amortized with Mo's algorithm (http://codeforces.com/blog/entry/7383). Here $c \geq 0.5$ and thus you might have known of this solution, but it may be worth sharing anyway.  
> **username_0**: @IvanSmirnov, yes, we are aware of that technique. Thanks for sharing anyway. :)  
> **username_3**: A 2-approximation in $Q(n) = \log{a} \log{n}$ is possible, but this isn't $\mathcal{O}(n^c)$.  

---

## 0 answers

