Restricted range minimum query

version 1.4.0.0 (8.7 KB) by Georgios Papachristoudis
Finds the position of the minimum element between two given indices in an array in constant time.

141 Downloads

Updated 22 Dec 2014

View License

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);

Cite As

Georgios Papachristoudis (2022). Restricted range minimum query (https://www.mathworks.com/matlabcentral/fileexchange/48842-restricted-range-minimum-query), MATLAB Central File Exchange. Retrieved .

MATLAB Release Compatibility
Created with R2014b
Compatible with any release
Platform Compatibility
Windows macOS Linux
Tags Add Tags
rmq

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!