一种基于稀疏表（Sparse Table）算法的方法：时间复杂度为
O( N x M x log(N) x log(M)) , O(1)。
预处理时间 -
O( N x M x log(N) x log(M))
查询时间 -
O(1)
理解该方法需要掌握使用稀疏表算法计算一维RMQ的知识。
我们可以使用2D稀疏表算法来查找范围最小查询(Range Minimum Query)。
一维情况下的操作：
我们使用动态规划对长度为 2^k 的子数组进行预处理以获取RMQ。我们将保留一个数组 M[0, N-1][0, logN]，其中M[i][j]是从i开始的子数组中最小值的索引。
为了计算M[i][j]，我们必须在区间的前半部分和后半部分中搜索最小值。显然，小块的长度为2^(j-1)，因此计算时的伪代码如下：
if (A[M[i][j-1]] < A[M[i + 2^(j-1) -1][j-1]])
M[i][j] = M[i][j-1]
else
M[i][j] = M[i + 2^(j-1) -1][j-1]
这里的A是存储值的实际数组。一旦我们对这些值进行了预处理，让我们展示如何使用它们来计算RMQ(i, j)。思路是选择完全覆盖区间[i..j]的两个块，并在它们之间找到最小值。让k = [log(j - i + 1)]。为了计算RMQ(i, j)，我们可以使用以下公式：
if (A[M[i][k]] <= A[M[j - 2^k + 1][k]])
RMQ(i, j) = A[M[i][k]]
else
RMQ(i , j) = A[M[j - 2^k + 1][k]]
对于二维数组：
类似地，我们可以扩展上面的规则到二维数组中。在这里，我们使用动态规划预处理长度为2^K, 2^L的子矩阵以进行RMQ，并保持一个数组M[0,N-1][0, M-1][0, logN][0, logM]。其中M[x][y][k][l]是从[x , y]开始且长度为2^K, 2^L的子矩阵中最小值的索引。
计算M[x][y][k][l]的伪代码如下：
M[x][y][i][j] = GetMinimum(M[x][y][i-1][j-1], M[x + (2^(i-1))][y][i-1][j-1], M[x][y+(2^(j-1))][i-1][j-1], M[x + (2^(i-1))][y+(2^(j-1))][i-1][j-1])
这里的GetMinimum函数将返回所提供元素中最小元素的索引。 现在我们已经预处理完毕，让我们看看如何计算RMQ（x，y，x1，y1）。 这里[x，y]是子矩阵的起始点，[x1，y1]表示子矩阵的结束点，即子矩阵的右下角点。 在这里，我们必须选择四个子矩阵块，它们完全覆盖[x，y，x1，y1]并找到它们的最小值。 让k = [log（x1-x + 1）]和l = [log（y1-y + 1）]。 为了计算RMQ（x，y，x1，y1），我们可以使用以下公式：
RMQ(x, y, x1, y1) = GetMinimum(M[x][y][k][l], M[x1 - (2^k) + 1][y][k][l], M[x][y1 - (2^l) + 1][k][l], M[x1 - (2^k) + 1][y1 - (2^l) + 1][k][l]);
以上逻辑的伪代码：
// remember Array 'M' store index of actual matrix 'P' so for comparing values in GetMinimum function compare the values of array 'P' not of array 'M'
SparseMatrix(n , m){ // n , m is dimension of matrix.
for i = 0 to 2^i <= n:
for j = 0 to 2^j <= m:
for x = 0 to x + 2^i -1 < n :
for y = 0 to y + (2^j) -1 < m:
if i == 0 and j == 0:
M[x][y][i][j] = Pair(x , y) // store x, y
else if i == 0:
M[x][y][i][j] = GetMinimum(M[x][y][i][j-1], M[x][y+(2^(j-1))][i][j-1])
else if j == 0:
M[x][y][i][j] = GetMinimum(M[x][y][i-1][j], M[x+ (2^(i-1))][y][i-1][j])
else
M[x][y][i][j] = GetMinimum(M[x][y][i-1][j-1], M[x + (2^(i-1))][y][i-1][j-1], M[x][y+(2^(j-1))][i-1][j-1], M[x + (2^(i-1))][y+(2^(j-1))][i-1][j-1]);
}
RMQ(x, y, x1, y1){
k = log(x1 - x + 1)
l = log(y1 - y + 1)
ans = GetMinimum(M[x][y][k][l], M[x1 - (2^k) + 1][y][k][l], M[x][y1 - (2^l) + 1][k][l], M[x1 - (2^k) + 1][y1 - (2^l) + 1][k][l]);
return P[ans->x][ans->y] // ans->x represent Row number stored in ans and similarly ans->y represent column stored in ans
}
X，存在一个简单的O(1)时间算法和O(MN)预处理。 - Evgeny Kluev