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:
- Is this method solving RMQ well known & common?
- How exactly is the update operation be done? I would be appreciate if someone can demonstrate with an update on index 5 (1-based)
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.)
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.
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.
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 usingmin(array[8], BIT1[4], BIT1[6], BIT1[7]).