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 2^k 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 2^j. 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 2^{j - 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=0; i<10; M[i++] = new int[logN]);

   

    // Generating Table of M[n][log(n)]

    for(int i=0; i<10; ++i)

        M[i][0] = i;

   

    for(int j=1; (1<<j) <= 10; ++j)

    {

        for(i=0; i+(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];

            else

                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 RMQ_A(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 RMQ_A(i, j) we can use the following formula:

Implementation of RMQ function is as follows:

int* RMQ(int *A, int size, int i, int j)
{

    int **M = preprocess(A, size);

    int k=0;

    while((1<<k++) < (j-i));

    --k;

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

        return A[M[i][k]];

    else

        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).