RMQ - Range Minimum Queries

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