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?
  • $\begingroup$ 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? $\endgroup$ – D.W. Oct 7 '16 at 0:59
  • $\begingroup$ @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. $\endgroup$ – Blue Bear Oct 7 '16 at 1:39
  • $\begingroup$ There is also a solution with $S(n) = O(n)$ and $Q(n) = O(\sqrt{n} \log n)$ amortized with Mo's algorithm (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. $\endgroup$ – Ivan Smirnov Oct 7 '16 at 12:09
  • $\begingroup$ @IvanSmirnov, yes, we are aware of that technique. Thanks for sharing anyway. :) $\endgroup$ – Blue Bear Oct 8 '16 at 15:37
  • $\begingroup$ A 2-approximation in $Q(n) = \log{a} \log{n}$ is possible, but this isn't $\mathcal{O}(n^c)$. $\endgroup$ – Antti Röyskö Jan 5 at 11:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.