# 4 ways to solve ±1 RMQ

You can test @ BNUOJ 4363 RE&MLE Quiz

Source code can be found @ Wiki

Test package(include data maker and source code) can be found @ Box

RMQ(Range Minimum/Maximum Query) is a kind of problem that asks you the minimum(for convenience) value in given intervals of a given array.

±1 RMQ is a special kind of RMQ that the difference between adjacent values is exactly 1.

For normal RMQ, we have ST(sparse table) algorithm.

Let f[i][j] be the minimum value of interval $$[i,i + {2^{j}})$$, which is

$f[i][j] = \min \{ {A_k}|i \le k < i + {2^j}\}$

so we have

$f[i][j] = \left\{ \begin{array}{l}{A_i},j = 0\\\min \{ f[i][j - 1],f[i + {2^{j - 1}}][j - 1]\} ,j > 0\end{array} \right.$

Hera we say

$f = RMQ(A)$

For each query [x, y], the answer is

$\min \{ f[x][k],f[y - {2^k} + 1][k]\}$ where $k = \min \{ j|{2^{j + 1}} \ge y - x + 1\}$

Apply to the problem I mentioned above, where there are at most N(1<=N<=1,000,000) numbers in the array and M(1<=M<=1,000,000) queries in total, we’ll need  f[MAXN][MAXE] where

$MAXN = N = 1,000,000$

$MAXE = {\log _2}^N \approx 20$

and another copy for maximum values which result in about 160 MB of memory, obviously beyond the limit.

If we can take doubling measure, why not triple or more? Similarly, we let p[i][j] denote the minimal value in range $$[i,i + {2^{5j}})$$, correspondingly we have

$f[i][j] = \left\{ \begin{array}{l}{A_i},j = 0\\\min \{ f[i + k \cdot {2^{5(j - 1)}}][j - 1]|0 \le k < {2^5}\} ,j > 0\end{array} \right.$

Queries can be similarly handled.

As Rujia Liu introduced in his book, we can divide the array into several blocks, each of

$l = {\log _2}^N/2$

numbers.

So there are

$N' = \left\lceil {\frac{N}{l}} \right\rceil = \left\lceil {\frac{{2N}}{{{{\log }_2}^N}}} \right\rceil \approx 100,000$

parts in total. Let A’ be the minimum value of each block

${A_i}' = \min \{ {A_j}|j \in [(i - 1)l + 1,il]$

Here we calculate

$f' = RMQ(A')$

Now for each query [x, y], first we find out where x, y is, say

x is the q1-th number in the p1-th block

y is the q2-th number in the p2-th block

the minimum value is

$answer = \min \left\{ \begin{array}{l}In - RMQ(p1,q1,l)\\In - RMQ(p2,1,q2)\\f'(p1 + 1,p2 - 2)\end{array} \right.$

here In-RMQ(i,j,k) means the minimum value from the j-th number to the k-th in block i.

And now we finally come to use the feature of ±1, the length of each block is l, so there are at most

${2^{l - 1}} = 512$

different blocks in essence. Calculate all the possible In-RMQ(i,j,k) queries in advance, save them in g[i][j][k].

Now all the queries can be done in O(1), and the preparation can be done in

$O(N'\log N' + {2^{l - 1}}{l^2}) = O(\frac{{2N}}{{\log N}}(\log N - \log \log N + 1) + \sqrt n {\log ^2}N) = O(N)$

So the complexity of the whole algorithm is O(N).

Actually, we can run faster if we use the most simple way to do the In-RMQ, enumerate, since l<10. Personally, I think it’s because of the addressing time for array g[][][], calculate g[][][] doesn’t take much time as I tested.

Here is the Test Result.

Corresponding to the order of the red text above, it’s

Sparse Table

Tricky1

±1RMQ & ±1RMQ + IO Optimize

Tricky2 & Tricky2 + IO Optimize

Well, the better ones get better opportunities.