Data Structures
Overview
Number
String
Array
Stack
Hash
Tree
Trie
Probabilistic Data Structures
Big O

RMQ - Range Minimum Queries

Updated: 2022-04-02
• Input: an array of numbers, of length n
• Output: given two integers a and b, return the minimum / maximum number in range [a, b]

https://www.topcoder.com/community/data-science/data-science-tutorials/range-minimum-query-and-lowest-common-ancestor/

Dynamic Programming

Note: here explains how to query the min value; to get the max value, simply replace Math.min() by Math.max().

init

Create a 2-dim lookup of size n by k, where k is the maximum integer such that 2^k <= N.

int k = (int) Math.floor(Math.log(n) / Math.log(2));
int[][] lookup = new int[n][k + 1];

Each number lookup[i][j] is the min/max value in range [i, i + 2 ^ j - 1], i.e. i is the starting point, and j defines the width of the range(2^j).

For j == 0, width is 1, each range contains only one element, so the min value is itself:

for (int i = 0; i < n; i++) {
lookup[i][0] = input[i];
}

Then we could iteratively calculate the min values by merging 2 sub-ranges(suppose we are querying min values):

for (int j = 1; j <= k; j++) {
// width of the sub-range: 2 ^ (j - 1)
int width = 1 << (j - 1);

for (int i = 0; i < (n - width); i++) {
lookup[i][j] = Math.min(lookup[i][j - 1], lookup[i + width][j - 1]);
}
}

Query

For each query [a, b], we can find the maximum width index k, then the original query can be described as 2 sub-queries, one aligned to the left and the other to the right, they may overlap but will always cover the whole original range.

e.g. query 1, 7, difference is 7 - 1 = 6, so k = 2 (since 2^3=8>6), so the query can be composed as 2 sub-queries of the same width 2^k=4: left-aligned [1, 4] and right-aligned [4, 7]

0123456789
----------
####
####

The code:

int k = (int) Math.floor(Math.log(b - a) / Math.log(2));
int min = Math.min(lookup[a][k], lookup[b - (1 << k) + 1][k]);

Full Code

public class RMQ {

private int[][] lookup;
private boolean queryMin;

public RMQ(int[] input, boolean queryMin) {

this.queryMin = queryMin;

int n = input.length;
int k = getIndex(n);

lookup = new int[n][k + 1];

for (int i = 0; i < n; i++) {
lookup[i][0] = input[i];
}

for (int j = 1; j <= k; j++) {
int width = 1 << (j - 1);
for (int i = 0; i < (n - width); i++) {
if (queryMin) {
lookup[i][j] = Math.min(lookup[i][j - 1], lookup[i + width][j - 1]);
} else {
lookup[i][j] = Math.max(lookup[i][j - 1], lookup[i + width][j - 1]);
}
}
}
}

public int query(int a, int b) {
int k = getIndex(b - a);
if (queryMin) {
return Math.min(lookup[a][k], lookup[b - (1 << k) + 1][k]);
} else {
return Math.max(lookup[a][k], lookup[b - (1 << k) + 1][k]);
}
}

/**
* Get the maximum k such that 2^k <= n
*
* @param n
* @return
*/
private int getIndex(int n) {
return (int) Math.floor(Math.log(n) / Math.log(2));
}
}