Range Minimum Query with point update using BIT

Revision en1, by BumbleBee, 2018-08-31 23:01:23

Recently I found this article which describes the way to perform range minimum query with point update using the binary indexed tree.

I understood the query part quite well, implemented it myself and solved some problems with it too. Here is my code.

But I am facing problems with the update function described in this article. First of all, they said that if we make two query calls in the update function the complexity will become O(log^2(n)). So they provided with an efficient way to update without using query calls to achieve an amortized complexity of O(log(n)). But I am neither being able to understand this part nor being able to implement it.

Can anyone explain this part in a better/easier way with the code of the update function implemented in the way described here?

Tags rmq, bit/fenwick tree


  Rev. Lang. By When Δ Comment
en1 English BumbleBee 2018-08-31 23:01:23 957 Initial revision (published)