2D阵列上的RMQ [英] RMQ on a 2d-Array

问题描述

我正在讲关于具有复杂度O(logn)的阵列上的RMQ这是sudo代码:

I am learing about RMQ on an Array which is having a complexity O(logn) Here is sudo Code:

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阵列吗?

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

Can i extend this concept for 2D Array i.e

Matrix of N x M. For a Submatrix of Length X which starts at position (a,b) i have to find the largest element present in a Submatrix.

推荐答案

是.

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

In your example Table[i][j] is the result of F for the range i..i+2^j.

因此在2D中，您需要具有 Table [x] [y] [j] ，这是子矩阵(x，y)的F的结果..(x + 2 ^ j)(y + 2 ^ j).

So in 2D you need to have Table[x][y][j] that is the result of F for the submatrix (x,y) .. (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])

这篇关于2D阵列上的RMQ的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！