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

Question

Continued from my last two questions, "Range Minimum Query approach (from tree to restricted RMQ)" and "Range Minimum Query approach (Last steps)"

I followed this tutorial on TopCoder, and the approach is introduced in the last section.

Now assuming I have everything done, and I am ready for query. According to the tutorial, this is what I should do:

i and j are in the same block, so we use the value computed in P and T

For example, if there's a block like this:

000111

The minimum value lies of course in the third 0, but if i and j are like 4 and 6, the third 0 won't lie in the queried criteria. Is my understanding wrong?

i and j are in different blocks, so we compute three values: the minimum from i to the end of i's block using P and T, the minimum of all blocks between i's and j's block using precomputed queries on A' and the minimum from the begining of j's block to j, again using T and P; finally return the position where the overall minimum is using the three values you just computed.

Why compute the minimum from i to end of i's block and the minimum of start of j's block to j? Don't the answer of both lies outside of i...j? Also, how to do that if it's not entirely a fit just like the last question.

Answer 1

The minimum value lies of course in the third 0, but if i and j are like 4 and 6, the third 0 won't lie in the queried criteria. Is my understanding wrong?

The idea is to precompute the RMQ for all pairs of indices in every possible block. As a result, regardless of what indices you query within that block, you should always be able, in O(1) time, to read off the RMQ of the two values within the block. In the case you listed in your question, the fact that indices 4 and 6 don't contain the block minimum is true but irrelevant. You'll already have the RMQ precomputed for indices 4 and 6.

Why compute the minimum from i to end of i's block and the minimum of start of j's block to j? Don't the answer of both lies outside of i...j? Also, how to do that if it's not entirely a fit just like the last question.

Consider this picture:

+------+------+------+------+------+------+
| ?i?? | ???? | ???? | ???? | ??j? | ???? |
+------+------+------+------+------+------+
   ^                            ^
   i                            j

If you want to solve RMQ(i, j), then the minimum could be in one of three places:

• In the same block as i, at an index from the position of i within its block to the end of its block,
• In the same block as j, at an index from 0 to the position of j within its block, or
• Somewhere in one of the middle three blocks.

The algorithm works by using the precomputed tables to solve the problem in the first two cases, then using the other algorithm to solve it for the third case. The minimum of these three should be your answer.

Hope this helps! This is by no means an easy algorithm, so please feel free to ask more questions here if you need help!