2d阵列上的RMQ

Question

我正在学习一个复杂度为O(logn)的数组上的RMQ，下面是sudo代码：

for i=0..N-1: // assuming Arr is indexed from 0
  Table[i][0] = F(Arr[i])
for j=1..k: // assuming N < 2^(k+1)
  for i=0..N-2^j:
    Table[i][j] = F(Table[i][j - 1], Table[i + 2^(j - 1)][j - 1])

我能否将此概念扩展到2D Array，即

N x M矩阵。对于从position (a,b)开始的Length X的子矩阵，我必须找到子矩阵中存在的最大元素。

Answer 1

是。

在您的示例中，Table[i][j]是范围i..i+2^j的F的结果。

所以在2D中，你需要有Table[x][y][j]，它是子矩阵(x，y)的F的结果。(x+2^j) (y+2^j)。

for j=1..k: // assuming N < 2^(k+1)
  for x=0..N-2^j:
    for y = 0..N-2^j:
      Table[x][y] = F(Table[x][y][j - 1], 
                      Table[x + 2^(j - 1)][y][j - 1],
                      Table[x][y+2&(j-1)][j-1],
                      Table[x+2^(j-1)][y+2^(j-1)][j-1])