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

但我看不出生成的 M 二维数组对计算 RMQ 有何帮助，我没有得到什么？

Answer 1

提示

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

完整答案

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

计算方式如下:

• 第一个 for 循环遍历所有元素并将范围 i..i 中的最小值分配给 i。这是因为单元素范围的最小值就是该元素。
• 嵌套循环然后为所有 k > i 计算其他范围 i..k 的 RMQ 答案。这是通过一次将一个元素扩展从 i 开始的已计算范围来完成的。