CODEWITHSUNDEEP
algorithm
Ming Tsai
Ming Tsai

Reputation: 307

Pre-processing code for RMQ Problem. What does it do?

This is taken from TopCoder's Algorithm page - section on "Trivial algorithms for RMQ" Supposedly a pre-processing function for calculating RMQ on the A array. 


 void process1(int M[MAXN][MAXN], int A[MAXN], int N)
  {
      int i, j;
      for (i =0; i < N; i++)
          M[i][i] = i;
      for (i = 0; i < N; i++)
          for (j = i + 1; j < N; j++)
              if (A[M[i][j - 1]] < A[j])
                  M[i][j] = M[i][j - 1];
              else
                  M[i][j] = j;
  }

But I don't see how the M 2D array generated would be helpful in calculating the RMQ, what am I not getting?

Upvotes: 1

Views: 505

Answers (1)

evgeny
evgeny

Reputation: 2584

Hint

The array A[] contains the sequence of elements that you calculate the RMQ for. The array M[][] contains answers for every query of type "What is the minimum element in range a..b?" into M[a][b].

Full answer

This way, you can look up the answer to any query on in constant time by looking at the respective element inside M[][].

The way it is calculated is as follows:

  • The first for-loop iterates over all elements and assigns the minimum of the range i..i to i. This is because the minimum of one-element-range is just that element.
  • The nested loops then calculate the RMQ answers for the other ranges i..k for all k > i. This is done by extending the already-calculated range that starts at i by one element at a time.

Upvotes: 2

Related Questions