Range Minimum Query <O(n), O(1)> approach (Last steps)

Question

Continued from my last question "Range Minimum Query approach (from tree to restricted RMQ)" (It's recommended to give it a read)

Again, from this tutorial on TopCoder, I have a few questions here and there, and I hope someone can clear them out.

So I transform a RMQ (Range Minimum Query) problem to a LCA (Lowest Common Ancestor) problem, and then transform it back, I can have an array that's simplified. (both transform can be found in the tutorial, and the simplified array is array L discussed in "From LCA to RMQ")

Anyway, I can get that array by using Euler Tour, and that's the core part of all the calculation.

First, I need to make it even simpler by making the whole array consists of only 1 and -1, so this is what I do: Ls[i] = L[i] - L[i-1].

The second step is actually partition, and that's simple enough, but there's this third step that confuses me.

Let A'[i] be the minimum value for the i-th block in A and B[i] be the position of this minimum value in A.

A refers to the L array in this sentence, so the minimum value would always be 1 or -1, and there's gonna be multiple 1s and -1s. It confuses me since I don't think this makes calculation easier.

The fourth step,

Now, we preprocess A' using the ST algorithm described in Section1. This will take O(N/l * log(N/l)) = O(N) time and space.

If A' only keep records of 1s and -1s, it would seemed useless to do anything on it.

The last step,

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.

What does it mean? To calculate each kind of combination? Like, 000 - 001 -.....?

It looks like multiple questions, but I was hoping that someone can just walk me thorough these last steps. Thanks!

Bragi

Answer 1

Hopefully this helps explain things.

A refers to the L array in this sentence, so the minimum value would always be 1 or -1, and there's gonna be multiple 1s and -1s. It confuses me since I don't think this makes calculation easier.

I think that the author is mixing up terms here. In this case, I believe that array A refers to the array of original values before they've been preprocessed into -1's and +1's. These values are good to have lying around, since having the minimum value computed for each block of the original array makes it a lot faster to do RMQ. More on that later. For now, don't worry about the +1 and -1 values. They come into play later.

If A' only keep records of 1s and -1s, it would seemed useless to do anything on it.

That's true. However, here A' holds the minimum values from each block before they've been preprocessed into -1 and +1 values, so this actually is an interesting problem to solve. Again, the -1 and +1 steps haven't come into play yet.

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.

This is where the -1 and +1 values come in. The key idea behind this step is that with small block sizes, there aren't very many possible combinations of -1's and +1's in a block. For example, if the block size is 3, then the possible blocks are

---
--+
-+-
-++
+--
+-+
++-
+++

Here, I'm using + and - to mean +1 and -1.

The article you're reading gives the following trick. Rather than using -1 and +1, use binary 0 and 1. This means the possible blocks are

000 = 0
001 = 1
010 = 2
011 = 3
100 = 4
101 = 5
110 = 6
111 = 7

The advantage of this scheme is twofold. First, since there are only finitely many blocks, it's possible to precompute, for each possible block, the RMQ answer for any pair of indices within that block. Second, since each block can be interpreted as an integer, it's possible to store the answers to these questions in an array keyed by integers, where each integer is what you get by converting the block's -1 and +1 values into 0s and 1s.

Hope this helps!

Schilling

A quick question though, how to get the minimum value in A fast? There's the old-school linear compare thing, is that good enough? – Bragi

@ShaneHsu- Yep, that's totally fine. The total size of all the blocks is O(n), so there's no reason to worry about this. – Schilling

Almost immediately, I had questions with query, there's a question in [rmq] if you like to take a look. – Bragi

"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" How? – Bragi

I don't get how its complexity is calculated, Is it done with ST? – Bragi

@ShaneHsu- The block size is log(N/2), so the number of possible blocks (since each block is all 0s and 1s) is 2^(log(N/2)) = (2^(log n))^(1/2) = n^(1/2) = sqrt N. The number of possible pairs of elements in a block of this size is O((log N)^2), so the total table size is O(sqrt(N) * (log N)^2). Since log N = O(n^(1/4)), this is O(sqrt N * (n^1/4)^2) = O(sqrt N * n^(1/2)) = O(sqrt N * sqrt N) = O(N). Phew! That was tricky. :-) – Schilling

Unlike other RMQ algorithm where they can also used to find maximum, I think this O(n) approach can only find minimum, right? Cause it seems weird to RMaxQ -> LCA. What do you think? – Bragi

@ShaneHsu- If you can solve RMinQ, you can always solve RMaxQ by negating all the values, then solving RMinQ on the new array. – Schilling