Friday, February 13, 2015

Range Minimum Query(RMQ)

Range Minimum Query (RMQ) is used on arrays to find the position of an element with the minimum value between two specified indices i.e. Given an array A[0,n-1] of n objects, Range Minimum Query from i to j asks for the position of a minimum element in the sub-array A[i, j].             


Preprocess RMQ:

The best approach  is to preprocess RMQ for sub arrays of length 2k using dynamic programming. Keep an array M[ 0, N-1 ] [ 0, logN ] where M[ i ] [ j ] is the index of the minimum value in the sub array starting at i having length 2j. Here is an example:


For computing M [ i ] [ j ] we must search for the minimum value in the first and second half of the interval. It's obvious that the small pieces have 2j - 1 length, so the recurrence is:

Implementation of the preprocessing function is as follows:

int** preprocess(int *A, int size)
    int **M = new int*[size];
    int logN = logbase2(size);

    for(int i=0i<10M[i++] = new int[logN]);
    // Generating Table of M[n][log(n)]

    for(int i=0i<10; ++i)
        M[i][0] = i;
    for(int j=1; (1<<j) <= 10; ++j)
        for(i=0i+(1<<j)-1 < 10; ++i)
            if(A[M[i][j-1]] <= A[M[i+(1<<(j-1))][j-1]])
                M[i][j] = M[i][j-1];
                M[i][j] = M[i+(1<<(j-1))][j-1];
    return M;

RMQ Function:

Once we have these values preprocessed, We can use them to calculate RMQA(i, j). The idea is to select two blocks that entirely cover the interval [i..j] and  find the minimum between them. Let k = [log(j - i + 1)]. For computing RMQA(i, j) we can use the following formula:

Implementation of RMQ function is as follows:

intRMQ(int *A, int size, int i, int j)

    int **M = preprocess(A, size);
    int k=0;
    while((1<<k++) < (j-i));

    if(A[M[i][k]] <= A[M[j-(1<<k)+1][k]])
        return A[M[i][k]];
        return A[M[j-(1<<k)+1][k]];

You can see the complexity of preprocess( ) function is O(nlogn) and complexity of RMQ function is O(1).

No comments:

Post a Comment