### safecomp's blog

By safecomp, history, 3 years ago, ,

hi everyone , this is my first blog post

recently i have read an excellent article about RMQ with BIT , It was thought that BIT is not suitable for solving minimum/maximum query , but this article show how we can solve RMQ with BIT efficiently

The paper show that the Binary Indexed Tree has the following advantages:

• Is faster than other data structures that allow the same types of operations.
• Can be adapted for a large number of distinct operations: sum, minimum, maximum, greatest common divisor (gcd), greatest common factor (gcf), etc.
• Can be extended on multi-core and distributed platforms.

so now i just want to share the link of paper to everyone who is interested in this topic

Effcient Range Minimum Queries using Binary Indexed Trees

•
• +17
•

 » 3 years ago, # |   0 I am not getting how update operation is done.Can you explain?
•  » » 3 years ago, # ^ |   0 sorry but i did not read it very carefully (yet) , i just share it ...
•  » » 3 years ago, # ^ |   0 this is what we should do (tell if i am wrong) for update operation suppose we want to change value at index p to newV (say A[p]=newV) , we should update all the tree nodes that have p in their subtree (just like a normal BIT) , so we should start by node p and go further (like normal BIT) , for each node in index x we should store two value (v,q) v is value of minimum in the interval which node x is responsible for and q is the index of the minimum in this interval , we know that any node x is responsible for interval like [n,m] where m=x , and we know that we can count number of members of this interval easily by count=(x&-x) operator , so we can obtain n=x-(count)+1 , there only one thing (but important) left , if q==p then we shoud update (v,q) as min(findMin(n,p-1),findMin(p+1,m)) but if q!=p that means the old min value was not in index p we shoul update (v,q) as min( (v,q) , (p,newV))