一种基于稀疏表(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