**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**. Here is an example:^{j}^{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:**

_{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:

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

## No comments:

## Post a Comment