How to do RMQ using two BITs?

Revision en1, by kirakira, 2017-03-10 17:38:17

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)
Tags #rmq, fenwick tree, binary indexed tree

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English kirakira 2017-03-10 17:38:17 950 Initial revision (published)