COME ON CODE ON

A blog about programming and more programming.

Range Minimum Query

with 13 comments

RANGE QUERY

Given a (big) array r[0..n-1], and a lot of queries of certain type. We may want to pre-process the data so that each query can be performed fast. In this section, we use T (f, g) to denote the running time for an algorithm is O(f(n)) for pre-processing, and O(g(n)) for each query.

If the queries are of type getsum(a, b), which asks the sum of all the elements between a and b, inclusive, we have a T (n, 1) algorithm: Compute s[i] to be the sum from r[0] to r[i-1], inclusive, then getsum(a,b) simply returns s[b+1]-s[a].

RANGE MINIMUM QUERY

For the queries of the form getmin(a,b) asks the minimum elements between r[a] and r[b], inclusive, the task is little more hard. The idea is always to get the min in some big ranges, so in the queries we may try to use these big ranges to compute fast. One simple algorithm is T (n,sqrt(n)): Break the n numbers into sqrt(n) regions, each of size sqrt(n). Compute the champion for each region. For each query getmin(a,b), we go from a towards right to the nearest station (at most sqrt(n) steps), then go by at most sqrt(n) stations (big regions) to the nearest station before b, and from there go to b.

Sparse Table (ST) Algorithm

A better approach is to preprocess RMQ for sub arrays of length 2k using dynamic programming. We will keep an array preProcess[0, N-1][0, logN] where preProcess[i][j] is the index of the minimum value in the sub array starting at i having length 2j. For example :

A[0] A[1] A[2] A[3] A[4] A[5]
2 4 3 1 6 7

For the above array the preProcess[1][0] = 1, preProcess[1][1]=2,preProcess[1][2]=3 and so on. Specifically, we find the minimum in a block of size 2j by comparing the two minima of its two constituent blocks of size 2j-1. More formally, preProcess[i, j] = preProcess[i, j -1] if A[preProcess[i, j -1]] <= A[preProcess[i+2j-1, j -1]] and preProcess[i, j] = preProcess[i+2j-1, j -1] otherwise.

Once we have these values preprocessed, let’s show how we can use them to calculate RMQ(i, j). The idea is to select two blocks that entirely cover the interval [i..j] and  find the minimum between them. We select two overlapping blocks that entirely cover the subrange: let 2k be the size of the largest block that fits into the range from i to j, that is let k = log(j – i). Then rmq(i, j) can be computed by comparing the minima of the following two blocks: i to i + 2k – 1 (preProcess(i, k)) and j – 2k + 1 to j (preProcess(j –2k +1, k)). These values have already been computed, so we can find the RMQ in constant time.

rmq

So as shown above if we need to calculate minimum between A[1] and A[5] we will take two sections of size 4 and compare their minimum values to get the answer. Below is a C++ template class implementation :

int preProcess[1000][10];
template
class RMQMin
{
  T *A;
  public:
    RMQMin(int N,T *array):A(array)
    {
        int i,j;
        for (i=0;i<N;i++)
            preProcess[i][0]=i;
        for (j=1; (1<<j)<=N; j++)
            for (i=0; i+(1<<j)-1<N; i++)
                preProcess[i][j]=
                A[preProcess[i][j-1]]<=
                A[preProcess[i+(1<<(j-1))][j-1]]?
                preProcess[i][j-1]
                :preProcess[i+(1<<(j-1))][j-1];
    }
   
    int query(int start,int end)
    {
        int diff=end-start;
        diff=31 - __builtin_clz(diff+1);
        return A[preProcess[start][diff]]
          <=A[preProcess[end-(1<<diff)+1][diff]]?
          preProcess[start][diff]
          :preProcess[end-(1<<diff)+1][diff];
    }
};

You can simply use the above class for any type of variable(numeric ofcourse). Just keep in mind that you have to declare a preProcess array of size N x log N . So it turns out that the space complexity of the algorithm is O(N log N) and time complexity T(NlogN, 1).

-fR0D

Advertisements

Written by fR0DDY

April 18, 2009 at 6:54 AM

Posted in Algorithm, Programming

Tagged with , , , , , , , ,

13 Responses

Subscribe to comments with RSS.

  1. >> Compute s[i] to be the sum from r[0] to r[i-1], inclusive, then getsum(a,b) simply returns s[a+1]-s[b]

    Looks like you mean it should return s[b+1]-s[a].

    Anton

    August 12, 2010 at 12:29 PM

  2. you mention “preProcess[1][0] = 1” and a couple of words later “preProcess[1][0] = 3”. The second time i think you meant “preProcess[3][0]”

    st0le

    April 6, 2011 at 10:15 AM

    • Hi,

      It was meant to be preProcess[1][2]=3. I have corrected it.

      fR0DDY

      April 6, 2011 at 8:13 PM

  3. hi, how can we use this concept to find the maximum element in a range?

    pranay

    June 2, 2011 at 11:17 PM

    • You just need to change some sign to find the maximum element. Try to figure out the algorithm and then you can see how to find the maximum element in a range.

      fR0DDY

      June 4, 2011 at 11:12 AM

  4. plzzz add some tut on binary indexed tree….

    aayush

    June 9, 2011 at 4:51 PM

  5. Nothing personal..am just curious!!!
    Why do I read your post that solves the problem with O(NlogN) time and needs additional memory of O(NlogN) instead of doing a simple linear search in O(N) time and with no memory overhead.

    pseudo code for linear search RMQ[A, i, j]:
    minPos=i, minVal=A[i]
    for each k i+1 to j
    if A[k]< minVal
    set minPos =k and minVal=A[k]
    end-if
    end-for

    kausik

    November 16, 2012 at 4:04 PM

    • Think about the case where the number of queries are very large. Your algorithm will take O(N) time for each query while the algorithm described above will take only O(1) time for each query.

      fR0DDY

      November 16, 2012 at 4:31 PM

      • thanks fR0DDY

        kausik

        November 17, 2012 at 8:18 AM

  6. What if we have more than 10^9 elements in array ?

    bit_cracker007

    December 10, 2012 at 12:23 PM

  7. hey can you help me on this
    what if i have to update the array

    how will i reflect in the table then??

    Aman Choudhary

    March 30, 2013 at 12:54 AM

  8. why this 31-(r-l+1)

    Kunal Prince

    February 6, 2016 at 9:36 PM


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: