## RMQ problem

Moderator: Board moderators

tryit1
Experienced poster
Posts: 119
Joined: Sun Aug 24, 2008 9:09 pm

### RMQ problem

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)

maxdiver
Learning poster
Posts: 51
Joined: Tue Sep 04, 2007 2:12 pm
Location: Russia, Saratov
Contact:

### Re: RMQ problem

You misunderstood a bit.
Of course, we find minima in original array, not in +-1 array.
But to find it efficiently, we exploit the fact, that each element a is a[i-1]+-1.
More precisely, we can divide array a[1..N] into blocks of length L=logn/2, and precompute RMQ in each block i between each pair (j,k).
But if we do this naively, then we'll get asymptotic about (N/L) * L^2 = N * L, that is not good enough.
And here we do an interesting trick: note that each block has length L=logn/2, that means that if we replace each block with its mask (got from +-1 representation) and first value of first element in block (because, +-1-representation is not enough to restore the block), than there could be only 2^L = 2^(logn/2) = sqrt(N) different masks.
This means that we don't have to precompute RMQ in each of N/L block, but only is those of them, that have unique masks (here we exploit the fact, that to find the position of RMQ we only need its mask, but not its first value).
So, we create a table t[sqrt(N)][L][L], and on the precomputing stage for each block we calculate its mask, and see, if t[mask] is already calculated, then skip this block - all information for RMQ in it has already been calculated before.

tryit1
Experienced poster
Posts: 119
Joined: Sun Aug 24, 2008 9:09 pm

### Re: RMQ problem

And here we do an interesting trick: note that each block has length L=logn/2, that means that if we replace each block with its mask (got from +-1 representation) and first value of first element in block (because, +-1-representation is not enough to restore the block), than there could be only 2^L = 2^(logn/2) = sqrt(N) different masks.

Few questions , if i give you a mask of +-1 , can you tell me where the minimum is ? Why isn't it ambiguous .

if the maks was 1 -1 -1 , the minimum is at position 2, if maks is 1 -1 1, minimum is at position 1 , but if mask is 1 -1 1 -1 ,minimum is at position 1 and 3 . In the original array position 1 and 3 can contain different values ?

So for mask t[100] =2, t[101]=1,t[1010]= ?

How about 1 1 -1 1 -1 -1 ? , 2 1 3 2 1 ? This is where i'm confused.

maxdiver
Learning poster
Posts: 51
Joined: Tue Sep 04, 2007 2:12 pm
Location: Russia, Saratov
Contact: