RMQ问题的预处理代码。是干什么的呢？

Question

这取自TopCoder的算法页面“RMQ的简单算法”一节，据说这是一个用于在A数组上计算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;
  }

​

但是我看不出生成的M2D数组对计算RMQ有什么帮助，我有什么不明白的？

Answer 1

提示

数组A[]包含要计算其RMQ值的元素序列。数组M[][]包含每个查询的答案，类型为“什么是范围a..b中的最小元素？”进入M[a][b]。

完整答案

这样，您就可以通过查看M[][]中的相应元素，在固定时间内查找任何查询的答案。

计算方法如下：

for循环的第一个循环遍历所有元素，并将范围i..i中的最小值分配给i。这是因为一个元素范围的最小值就是那个元素。

• 嵌套循环，然后计算其他范围i..k k > i的RMQ答案。这是通过将已经计算好的从i开始的范围一次扩展一个元素来实现的。