File Exchange

image thumbnail

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.

1 Download

Updated 22 Dec 2014

View Version History

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 (2021). Restricted range minimum query (https://www.mathworks.com/matlabcentral/fileexchange/48842-restricted-range-minimum-query), MATLAB Central File Exchange. Retrieved .

Comments and Ratings (4)

Hi Stephen, thanks for your kind words! I always look forward to getting constructive feedback and strive to improve my submissions. I hope I get the time to polish some of my work and upload it in the future. Happy New Year!

Stephen Cobeldick

Thank you for your prompt response and explanation: it is reassuring to know that there *is* a difference. Actually I did read more than just the summary, but sometimes users do not seem to realize that they can update their submissions and instead submit twice, the second time after editing for clarity or accuracy. Indeed the differences between the descriptions of these two submissions is rather subtle, even after reading it several times. I apologize for assuming the worst.

Your submissions look very nice, however as I know nothing of this area of mathematics I will leave the first rating up to some else. Happy New Year!

Hi Stephen, probably you only read the summary and not the description of the submission. Summary accepts only 100 chars, so I could not describe there the subtle differences between Restricted RMQ and RMQ, but only the main task of the function. In general, RMQ function generates intermediate structures, which then allow you to determine the index of the minimum element between any two indices of the array in constant (instead of linear) time.

Had you read the description, you would see that Restricted RMQ supports only arrays whose consecutive elements differ by +1 or -1, while RMQ supports any array. In that respect, RMQ is a superset of Restricted RMQ but they differ in time and space complexity. RMQ runs in O(N logN) time and requires O(N logN) space, while Restricted RMQ requires O(N) time and space. Restricted RMQ supports only a very special type of arrays (arrays whose consecutive elements differ by +1 or -1), but these arrays are generated when we solve the Lowest Common Ancestor (LCA) problem. In other words, there is a way to solve the LCA problem by converting to RMQ. Because this conversion leads to this special type of arrays, we can use the Restricted RMQ instead of RMQ to solve the LCA problem. (Of course, as I found empirically, lower asymptotic complexity does not always translate to lower (actual) running times, because the latter depends on constant factors as well as other factors.)

The "broken URL" had been fixed. You can click on the URL, listed in the description to learn more about the RMQ problem and the conversion from LCA to RMQ.

Thanks,
Giorgos

Stephen Cobeldick

What is the difference between this submission (FEX 48842) and your previous one titled "Range minimum query" (FEX 48841)? The presence of two very similar submissions without any explanation of their differences is not encouraging: should I try to figure out for myself what the differences are? If 48842 is supposed to supersede 48841, then please delete 48841 from FEX and in future only use the update functionality provided by MATLAB FEX.

You remark in your "Updates" that "The url is broken. Trying to fix it.": URL highlighting and linking is provided by the browser and not by FEX. As the URL you are using includes a space character there may be nothing you can do to force browsers to accept this as being part of one URL. Perhaps placing it on its own line (all by itself), or following it by the '.html'/'.asp' (or whichever appropriate filetype) may help.

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!