algorithm - RMQ问题的预处理代码。它有什么作用？

这摘自topcoder的算法页面-“rmq的平凡算法”部分
假设是一个预处理函数，用于计算数组上的rmq。

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

但是我不明白生成的M 2D数组如何有助于计算RMQ，我没有得到什么？

最佳答案

暗示
数组A[]包含计算rmq的元素序列。数组M[][]包含“a..b范围内的最小元素是什么”类型的每个查询的答案进入M[a][b]。
完整答案
这样，您可以通过查看M[][]中的相应元素，在恒定时间内查找任何查询的答案。
计算方法如下：
第一个for循环遍历所有元素，并将i..i到i范围的最小值指定给这是因为一个元素范围的最小值就是那个元素。
然后，嵌套循环计算所有i..k的其他范围k > i的rmq答案。这是通过一次将从i开始的已计算范围扩展一个元素来完成的。