one0one's blog

Help for an <O(n), O(1)> solution for range minimum query
By one0one, history, 7 years ago, In English

Currently, I am researching about range minimum query. I read the topcoder article. At the end of the article there is an <O(n), O(1)> solution for the restricted RMQ.

I didn't understand the article and I have googled it but what I have found was too complex for me. I am a newbie so I need some simple explanations or sources.

  • Vote: I like it
  • +8
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
7 years ago, # |
  Vote: I like it +15 Vote: I do not like it

It's actually not the kind of topic to start with :) And I've never seen anyone implementing it at a real contest since there are lots of simpler methods for both rmq and lca.

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

First, you don't need it in real contests. Sparse table or segment tree is more than enough.
Second, IIRC topcoder article describes Farach-Colton&Bender algorithm. But it can be simplified, read this paper (particularly section 3.2)

→ Reply
»
7 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Good day to you!

This <O(n),O(1)> RMQ is for LCA only. It isn't standard RMQ (sparse table) because it uses a "property" of euler walk in tree. The property is that every "adjacent" node's number (which is height) differs by 1 (exactly — each time "1" or "-1").

You can use this property to "precalculate" short sequences (recommended length is log(N)/2) of consecutive nodes. You can make table, which can tell you (for each such sequence) the "highest" node in it. FOR EXAMPLE the table could be [K]*[K]*[2^K] (but it can be done even better) [where K is chosen length mehrunesartem(N)/2] in which you state START/END/BITMASK and get answerin O(1) [of the highest node in such bitmask]. {as you can see, this table will be lesser than N for bigger values and can be pre-calculated in same time as its size} [improvement could be fact that you need only two types of queries: something→end /or/ begin→something, so you can reduce it by another K]

Anyway point of this is, that you can just "make a note" of the highest element in each such sequence AND make CLASSICAL RMQ (sparse table) ONLY over such values. As you can see, RMQ precalculation is O(Nlog(N)) and you are aplying it to sequence of size 2*N/log(N), which makes it O(2*Nlog(N/log(N)/log(N)) which is also lesser than "N".

Now you will asnwer queries in such way, that you "round" the queries by "modulo" log(N), make O(1) query to sparse table on such rounded query AND then two O(1) queries (to the part you rounded) into the TABLE.

So — that's it — but as others said above, it is advanced topic, since you need to learn "sparse table" and "euler tour on tree" before starting this. Also as someone mentioned, it is "overkill" in CP (unless you want to hunt times).

Also sorry since I'm not so good in exmplanations.

Good Luck & Have Nice Day!

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it +2 Vote: I do not like it

    Hi -Morass-, I know sparse table and euler tour on tree but they are not enough to understand your explanation for me. If you have visual explanation or source codes, it would be better. By the way, thank you for answer. I will read few more times maybe I can understand.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Here shall be the code for it.

      As I said it is advanced (and not much necessary). Anyway don't hessitate to pose some question about what is unclear — and I could try to explain (even though it might make it worse {with respect to my explanation skills :P })

      ~/Morass

      → Reply