### RMQ problem

Posted:

**Fri Dec 19, 2008 10:05 pm**i read the RMQ problem from TC. From the section

http://www.topcoder.com/tc?module=Stati ... cted%20RMQ.

i understand most of it except

It remains now to show how the in-block queries can be made. Note that the length of a block is l = [(log N) / 2], which is quite small. Also, note that A is a binary array. The total number of binary arrays of size l is 2^l=sqrt(N). So, for each binary block of size l we need to lock up in a table P the value for RMQ between every pair of indices. This can be trivially computed in O(sqrt(N)*l^2)=O(N) time and space. To index table P, preprocess the type of each block in A and store it in array T[1, N/l]. The block type is a binary number obtained by replacing -1 with 0 and +1 with 1.

I don't quite get this. Can you please elaborate ?

say we have block like 1 2 3 4 3 4 3 2 1, the +/-1 array would be

1 1 1 1 -1 1 -1 -1 -1, how to calculate the minimum value between 2 and 6.

ie 1 1 -1 1 -1 -1

Can we take any of the -1 values ? Why would any of them be okay ? The LCA of 2 nodes is a single node there is no ambiguity about it.

So we if have some like 1 -1 1 , it is always going to be index 1 ,

how can we guarantee that part ?

how to compute minimum for 1 -1 -1 -1 1 1 1 for the values (0,6)

http://www.topcoder.com/tc?module=Stati ... cted%20RMQ.

i understand most of it except

It remains now to show how the in-block queries can be made. Note that the length of a block is l = [(log N) / 2], which is quite small. Also, note that A is a binary array. The total number of binary arrays of size l is 2^l=sqrt(N). So, for each binary block of size l we need to lock up in a table P the value for RMQ between every pair of indices. This can be trivially computed in O(sqrt(N)*l^2)=O(N) time and space. To index table P, preprocess the type of each block in A and store it in array T[1, N/l]. The block type is a binary number obtained by replacing -1 with 0 and +1 with 1.

I don't quite get this. Can you please elaborate ?

say we have block like 1 2 3 4 3 4 3 2 1, the +/-1 array would be

1 1 1 1 -1 1 -1 -1 -1, how to calculate the minimum value between 2 and 6.

ie 1 1 -1 1 -1 -1

Can we take any of the -1 values ? Why would any of them be okay ? The LCA of 2 nodes is a single node there is no ambiguity about it.

So we if have some like 1 -1 1 , it is always going to be index 1 ,

how can we guarantee that part ?

how to compute minimum for 1 -1 -1 -1 1 1 1 for the values (0,6)