BumbleBee's blog

By BumbleBee, history, 12 months ago, In English,

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?

 
 
 
 
  • Vote: I like it
  • -10
  • Vote: I do not like it

»
12 months ago, # |
  Vote: I like it -10 Vote: I do not like it

10 hours and still no help. This is frustrating.

»
12 months ago, # |
  Vote: I like it +1 Vote: I do not like it