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)*l2)=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 value between 2 and 6.
ie 1 1 -1 1 -1 -1