kirakira's blog

How to do RMQ using two BITs?
By kirakira, history, 7 years ago, In English

I know RMQ normally is solved by some maybe more complicated data structures like segment tree, yet sometime ago I found this paper online: http://www.ioinformatics.org/oi/pdf/v9_2015_39_44.pdf

It shows a way to use two BITs to find the RMQ (though only support point update, not range update).

I have read through the paper several times, I understand how to build the BITs and how to query it, but I totally don't know how to update it. I have post a question on Stack Overflow about this too but seems the answer is not fully convincing.

Therefore I would like to know:

  1. Is this method solving RMQ well known & common?
  2. How exactly is the update operation be done? I would be appreciate if someone can demonstrate with an update on index 5 (1-based)
  • Vote: I like it
  • +10
  • Vote: I do not like it

»
7 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

To answer the first question: The method is know, but not well known. I've seen multiple posts reference this paper, but I haven't actually seen an implementation of it.

The approach might be theoretically interesting, but practically I would always use a segment tree. The only real advantage a BIT has over the Segment tree is that it uses less memory. But if you have to use two BITs, than the advantage disappears, since a (bottom up) segment tree implementation also only needs 2*n memory. (Btw, I wouldn't say that segment tree is a more complicated data structure than BIT, in fact I find it is much easier data structure.)

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

    BIT's big advantage is its implementation speed. If you only need prefix sums and not much else, then you can implement it in like a minute. Segment trees aren't very difficult, but they still take more time to implement.

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

Here is an implementation: RMQ_BIT_vs_ST. I've included a benchmark to compare the speed of the BIT implementation and the Segment tree implementation, because I didn't believe the numbers stated in the paper.

I suspect that they used a top-down version of the segment tree. In my benchmark I used both the top-down version and the bottom-up version.

My results: Queries are 68% faster than bottom-up ST and 88% faster than top-down ST (paper stated 77%). Updates are 65% slower than bottom-up ST but 82% faster than top-down ST (paper stated 47% faster).

Conclusion: I was pretty surprised that queries using BIT are so fast. Even compared to the bottom-up ST. However updates are still slower compared to the bottom-up ST. The reason is, that updates on BIT are more complicated. Even though they have the same amortized time complexity the overhead of the BIT is bigger. Recompute the minimum of a segment requires O(log n) time in a BIT, while in the Segment Tree you always can do it in O(1). I'll definitely keep using a Segment Tree, because the implementation for RMQ using BIT is way too tedious.

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

And to answer the second question: You need to update the segments 5, 6, 8, 16, ... in BIT1, and the segments 5, 4 in BIT2.

Now how you update the segments, and if you have to update them depends on the old values of the array and the new value.

Here just an example: lets say the segment 8 (which is the range [1, 8]) had the minimum 1 and you replaced the value 1 with a 2. Then you need to recompute the segment using min(array[8], BIT1[4], BIT1[6], BIT1[7]).

→ Reply