Range minimum problem (general case)

The Range Minimum Problem is defined as: Given an array A[1..n] of real numbers, we want to preprocess A such that for any two given integers i and j with 1 ≤ i < j ≤ n we can efficiently compute an integer k, i ≤ k ≤ j for which A[k] is minimum.


Here I am going to go over three solutions which use preprocessing to provide a O(1) per query operational time.


Solution 1:
This is the most brute of the three solution. It takes O(n^2) time and space.
It consists in storing the answer for all possible n-choose-2 pairs of (i,j) possible.
For this we make a two dimensional array X defining X[i][j] as:


X[i][j] = k ∈ [i,j] s.t. A[k] is minimum.


We construct X as shown in the recurrence relation shown in this figure.


Solution 2:
This solution is slightly smarter and takes O(n log n) time and space.
Here an array Y is defined as follows:


Y[i][l] = k ∈ [i, i + 2^l - 1] s.t. A[k] is minimum, for i∈[1,n-1] and l∈[1, log(n-i+1)]


For ease of exposition, by log(x) we mean floor of log(x) in this post.


Observe that for integers i and j in the interval [1,n] such that i < j, for h = log(i-j) we have that {i,i+1,...,i + 2^h - 1} ∪ {j - 2^h + 1,...,j} = [i,j].


Then min(A[Y[i][h]], A[Y[j-2^h+1][h]]) is the minimal element in A[i..j].


We construct Y as shown the recurrence relation in this figure.


All for now folks.


MArio