Given an array A[1...N], it finds the position of the element with the minimum value between two given indices.
It returns the answer in constant time. It only works for arrays whose consecutive elements differ either by +1 or -1.
The restricted RMQ problem can be used to recover the lca (lowest common ancestor) in a graph in constant time. See <http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor#A%20O(N),%20O(1)%20algorithm%20for%20the%20restricted%20RMQ%20for%20more%20details Restricted RMQ>.
Time complexity: O(N)
Space complexity: O(N)
Example
A = [0 1 2 3 2 3 2 1 2 1 2 1 0 1 2 1 2 1 0];
N = length(A); % length of original array A
bs = ceil(log2(N)/2); % block size
[A_blk,I_blk,M_blk,T,I,blkstart] = rmq_restr(A);
% Find the position of the minimum element between indices i, j
i = 2;
j = 6;
i1 = ceil(i/bs);
i2 = ceil(j/bs);
% Blocks between block of i and block of j
if i2-i1 > 2 % there are intermediate blocks [i1+1...i2-1] between positions i and j
k = floor(log2(i2-i1-2));
if A_blk(M_blk(i1+1,k+1)) <= A_blk(M_blk(i2-1-2^k+1,k+1))
i_m = I_blk(M_blk(i1+1,k+1));
else
i_m = I_blk(M_blk(i2-1-2^k+1,k+1));
end
Am = A(i_m);
elseif i2-i1 == 2 % there is only one intermediate block between positions i and j
i_m = I_blk(M_blk(i1+1,1));
Am = A(i_m);
else % positions i,j either belong to neighboring blocks or to the same block
i_m = -1;
Am = Inf;
end
if i1 ~= i2
% Left sub-block [i...blkstart(i1+1)]
i_l = T(i-blkstart(i1)+1, bs, I(i1));
i_l = blkstart(i1) + i_l -1;
Al = A(i_l);
% Right sub-block [blkstart(i2)...j]
i_r = T(1, j-blkstart(i2)+1, I(i2));
i_r = blkstart(i2) + i_r -1;
Ar = A(i_r);
else % both i and j belong to the same block
% Left sub-block: represents block of i and j
i_l = T(i-blkstart(i1)+1, j-blkstart(i1)+1, I(i1));
i_l = blkstart(i1) + i_l -1;
Al = A(i_l);
% Right sub-block: does not exist
i_r = -1;
Ar = Inf;
end
i_tri = [i_l, i_m, i_r];
A_tri = [Al, Am, Ar];
[~,i_min] = min(A_tri);
idx = i_tri(i_min);