fnf47's blog

By fnf47, 18 months ago, In English,

2D Range minimum Query in <O(n*m*logn*logm),O(1)>

I solved THIS problem from "codechef June16 long challenge" by extending the " 1D RMQ sparse table method" to 2D version which finds maximum value in a submatrix in O(1) after O(n*m*logn*logm) preprocessing time.

1D RMQ <O(n*logn),O(1)>

Problem: Given an array[n] and Q queries. Each query asks for minimum in range x to y where 0=<x<=y<n

Preprocess : O(n*logn)

 For(i=0;i<n;i++)            
   table[ 0 ][ i ]=array[ i ]         //building base

 For(j=1;j<=log(n);j++)
   For(i=0;i+2^(j-1)<n;i++)          
     table[ j ][ i ] = min ( table[ j-1 ][ i ], table[ j-1 ][ i+2^(j-1) ] )  //use previously computed

we created a sparse table[ 1+logn ][ n ]
table[ j ][ i ] contains the minimum value in range i to i-1 + 2^j inclusive
Each range is a power of 2. First we build base of the table. Then for each range we split it into 2 equal parts for which value is already calculated. This way table is build in O(n*logn).

Query(x,y) : O(1)

     len=y-x+1
     k=log2(len)
     return min(table[ k ][ x ],table[ k ][ y+1-2^k ])   // ranges may overlap

Query is then simply splitting the range in 2 parts each of which is a power of 2 and then using the pre-computed value from table. The 2 partitioned Ranges may overlap.

I found THIS video which explains it in detail
This was 1D RMQ. Now lets extend this concept to solve 2D RMQ


2D RMQ <O(n*m*logn*logm),O(1)>

Problem:Given a matrix[n][m] and Q queries. Each query asks for minimum in submatrix[ (x1,y1), (x2,y2) ]
x1,y1 is the top left-most point and x2,y2 is bottom right-most point of the submatrix.Assume 0-based indexing

Preprocess : O(n*m*logn*logm)

  • we create a table[ 1+logn ][ n ][ 1+logm ][ m ]
  • Each box of the table[ 1+logn ][ n ] is a sparse table of size [ 1+logm ][ m ]
  • Let us see what table[ jr ][ ir ][ jc ][ ic ] actually contains:
    It contains the minimum element from column ic to ic-1+2^jc of all rows from ir to ir-1+2^jr
    In other words, it contain the minimum element in the submatrix [ (ir,ic), (ir-1+2^jr , ic-1+2^jc) ]
    where submatrix [ (x1,y1),(x2,y2) ] denotes the submatrix with x1,y1 as its top left-most and x2,y2 as its bottom right-most point.
  • Now you can easily conclude that, table[ 0 ][ ir ][ jc ][ ic ] is nothing but the 1D RMQ table if we take our array as row ir

Now,lets see how to code it

At First,for each row ir, we compute table[ 0 ][ ir ][ jc ][ ic ] ,the same as we did in 1D version.
Taking each row as an array and then computing its sparse table in same fashion as in 1D RMQ.

For(ir=0;ir<n;ir++)
{
  For(ic=0;ic<m;ic++)
    table[ 0 ][ ir ][ 0 ][ ic ] = Matrix[ ir ][ ic ];
       
  For(jc=1;jc<=log2(m);jc++)
    For(ic=0;ic+2^(jc-1)<m;ic++)
     table[0 ][ir ][jc ][ic ] = min(table[0 ][ir ][jc-1 ][ic ],table[0 ][ir ][ jc-1 ][ ic+2^(jc-1) ])
}        

The above step is nothing but computing the sparse table for each row.
The complexity for one row is O(m*logm) and so for all rows O(n*m*logm).

Now,we will use this base to build the entire table.

For(jr=1;jr<=log(n);jr++)
  For(ir=0;ir<n;ir++)
    For(jc=0;jc<=log(m);jc++)
      For(ic=0;ic<m;ic++)
        table[jr ][ir ][jc ][ic ] = min(table[jr-1 ][ir ][jc ][ic ],table[jr-1 ][ir+2^(jr-1) ][jc ][ic ])  

Its not very difficult to understand this,just go through each line of the above code and try to visualise.

Clearly,the above step is O(n*m*logn*logm)

Query(x1,y1,x2,y2) : O(1)

We have to find the minimum in submatrix [(x1,y1),(x2,y2)]

    lenx=x2-x1+1
    kx=log2(lenx)
    leny=y2-y1+1
    ky=log2(leny)

First we will query on n
we have to query from row x1 to row x2.
But we have only computed for the range which are powers of 2 so we will divide in into two range
each of which is a power of 2.

x1 to x1-1+2^kx .....(say range R1)
x2+1-2^kx to x2 .....(say range R2)

The partition may overlap but that's not the problem here as we have to find the min/max only.

Now for each of the above two ranges R1 and R2, we have to query in column y1 to y2.
For this we will do the same range partition as we did above, i.e.

y1 to y1-1+2^ky ......(say range C1)
y2+1-2^ky to y2 ......(say range C2)

so query is simply 3 lines of code,

  min_R1 = min ( table[kx ][x1 ][ky ][y1 ] , table[kx ][x1 ][ky ][ y2+1-2^ky ] ) 
  min_R2 = min ( table[kx ][x2+1-2^kx ][ky ][y1 ], table[kx ][x2+1-2^kx ][ky ][y2+1-2^ky ] )
  return min ( min_R1, min_R2 )

Done.

We can also use 2D segment tree to solve 2D RMQ in <O(n*m), O(logn*logm)>. It has a special benefit that we can also do update in O(logn*logm). We will see that in next blog.

1D RMQ Video
1D RMQ problem //use fats I/O

2D RMQ problems
problem1 // 2D segtree gives TLE in last subtask
problem2

 
 
 
 
  • Vote: I like it  
  • +90
  • Vote: I do not like it  

»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

awesome ...very informative

»
18 months ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

thanks very much , I didn't even think about the 2D version before. Now I learnt it :)

I am waiting for your next blog ...

  • »
    »
    18 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Glad that it helped :) I will write the next blog soon.

»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks a ton for this :) Could you please elaborate a little bit on the fourth point of preprocess? "Now you can easily conclude that, table[ 0 ][ ir ][ jc ][ ic ] is nothing but the 1D RMQ table if we take our array as row ir" Not quite able to get it here.. Thanks!

  • »
    »
    18 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    suppose ir=0.
    Now take row 0 i.e the first row as your array[ ]. Build its sparse table[ 1+logm ][ m ] as we did in 1D RMQ problem for array[ n ]. Store this sparse table in table[ 0 ][ 0 ][ 1+logm ][ m ].

    For ir=1
    Do the same as above just consider your array as row 1 i.e the 2nd row. Store this in table[ 0][ 1][ 1+logm][ m].

    ...and so on for all ir < n.

    • »
      »
      »
      18 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks! Its crystal clear now :) Also I do not get how is the querying done in O(1). Shouldn't it be O(logN) in the case of 1D RMQ?

»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I coded it and was giving TLE during preprocessing, I wondered if 10^8 array construction was doing this since lots of memory had to be moved around.

Code : 2D RMQ solution TLE

  • »
    »
    18 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    To make this post easy to understand I have taken the table[ 1+logn][ n][ 1+logm][ m ] But if you take it as
    table[ 1+logn][ 1+logm][ n][ m] it will be faster. You have taken it as table[ n][ m][ 1+logn][ 1+logm] which is slow.

    see here and here

  • »
    »
    18 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Even I had the same issues , I made the following changes and was able to get AC : 1. Precompute log values (till around 2000) and store them in an array 2. Access the matrix in row major way . (Accessing in column major way leads to many cache misses )

    My AC solution : LINK

  • »
    »
    15 months ago, # ^ |
    Rev. 2   Vote: I like it +9 Vote: I do not like it

    You can also find the minima / maxima on subarrays of size axb from a matrix of size NxM in O(N * M) time using deques (the problem is a generalization of the one-dimensional case). This way you can remove the RMQ preprocessing and improve a lot of time cache-wise even.

    Code: https://www.codechef.com/viewsolution/11535531

»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Another problem to practice — 15D - Map

»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

This the thing which I am searching for. Thank you @fnf

»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In simple sparse table implementation, you wrote 'i+2^(j-1) <n' while on one of topcoder tutorial it is 'i +2^j -1 < n' , are both correct ? How? https://www.topcoder.com/community/data-science/data-science-tutorials/range-minimum-query-and-lowest-common-ancestor/#Sparse_Table_(ST)_algorithm

»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Actually , you shouldn't use log2() function, as its complexity is O(log2(N)) not O(1) . So, your query complexity is still O(log(N)) not O(1) . I got TLE while solving problem 1 in contest time for this reason.

»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Awesome, But Your 2D sparse table code is not giving correct output for rectangle.

»
13 months ago, # |
  Vote: I like it -8 Vote: I do not like it
For(jr=1;jr<=log(n);jr++)
  For(ir=0;ir<n;ir++)
    For(jc=0;jc<=log(m);jc++)
      For(ic=0;ic<m;ic++)
        table[jr ][ir ][jc ][ic ] = min(table[jr-1 ][ir ][jc ][ic ],table[jr-1 ][ir+2^(jr-1) ][jc ][ic ])

In this above snippet, won't ir+2^(jr-1) exceed the value of n and cause a segfault?
Please do help me with the problem: http://codeforces.com/contest/713/problem/D

  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I left it on purpose not to make the snippet complicated.The snippet was to make you understand the logic in simple way. You can check for corner case yourself. Like in second loop replace ir<n to ir+2^(jr-1)<n or you can take extra size array.

»
4 months ago, # |
Rev. 2   Vote: I like it -7 Vote: I do not like it

Another Problem To Pratice — https://www.codechef.com/problems/FRMQ