# RMQ - Range Minimum Queries

Last 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] = 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] = 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));
}
}
``````