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)