CODEWITHSUNDEEP
algorithm
user6250837
user6250837

Reputation: 468

RMQ on a 2d-Array

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])

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.

Upvotes: 0

Views: 782

Answers (1)

Sorin
Sorin

Reputation: 11968

Yes.

In your example Table[i][j] is the result of F for the range i..i+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])

Upvotes: 1

Related Questions