Код предварительной обработки для RMQ Проблема. Что оно делает?

Question

Это взято со страницы Алгоритм TopCoder - раздел «Тривиальные алгоритмы для RMQ» Предположительно, функция предварительной обработки для вычисления RMQ на массиве A.

<code>
 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;
  }

Но я не вижу, как сгенерированный двумерный массив мог бы помочь в вычислении RMQ, что я не получаю?

Answer 1

Подсказка

Массив A[] содержит последовательность элементов, для которой вы рассчитываете RMQ.Массив M[][] содержит ответы на каждый запрос типа "Каков минимальный элемент в диапазоне a..b?"в M[a][b].

Полный ответ

Таким образом, вы можете найти ответ на любой запрос в постоянное время, посмотрев на соответствующий элемент внутри M[][].

Способ его вычисления следующий:

• Первый цикл for перебирает все элементы и присваивает минимум диапазона от i..i до i.Это связано с тем, что минимум одного элемента-диапазона является именно этим элементом.
• Затем вложенные циклы вычисляют ответы RMQ для других диапазонов i..k для всех k > i.Это делается путем расширения уже рассчитанного диапазона, который начинается с i на один элемент за раз.