Geek Answers Handbook

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

Continuation of my last two questions: Minimum Range Query Approach (from tree to limited RMQ) "and" Minimum Query Range (last steps) "

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

Now, believing that everything is done, and I am ready for the request. According to the tutorial, this is what I have to do:

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

For example, if there is such a block:

000111

The minimum value, of course, lies in the third 0, but if I and j are 4 and 6, then the third 0 will not lie in the requested criteria. Am I mistaken in my understanding?

i and j are in different blocks, so we calculate three values: the minimum from i to the end of the i-block using P and T, the minimum all the blocks between blocks i and j using pre-calculated queries on A 'and the minimum from the beginning of j block to j, again using T and P; finally, return the position where the total minimum uses the three values ​​you just calculated.

Why calculate the minimum from i to the end of the i block and the minimum of the start of the j block to j? Doesn't the answer lie outside i ... j? In addition, how to do it, if it does not quite fit as a last question.

+4
source share
1 answer

The minimum value, of course, lies in the third 0, but if I and j are 4 and 6, then the third 0 will not lie in the requested criteria. Am I mistaken in my understanding?

The idea is to precompute RMQ for all index pairs in all possible blocks. As a result, no matter what indexes you request in this block, you should always be able to read RMQ from two values ​​inside the block during O (1). In the case indicated in your question, the fact that indices 4 and 6 do not contain a minimum block is true, but it does not matter. You will already have RMQ pre-calculated for indices 4 and 6.

Why calculate the minimum from i to the end of the i block and the minimum of the start of the j block to j? Doesn't the answer lie outside i ... j? In addition, how to do it, if it does not quite fit as a last question.

Consider this image:

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

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

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

The algorithm works using pre-computed tables to solve the problem in the first two cases, and then using another algorithm to solve it for the third case. The smallest of these three should be your answer.

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

+3
source

More articles:


All Articles