safecomp's blog

By safecomp, history, 3 years ago, In English,

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

 
 
 
 
  • Vote: I like it  
  • +17
  • Vote: I do not like it  

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I am not getting how update operation is done.

Can you explain?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    sorry but i did not read it very carefully (yet) , i just share it ...

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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))

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    If you only allow increments for a maximizing tree or decrements for a minimizing tree, then you can simply update each BIT and the data array independently, the same way a summing BIT is updated.

    What the paper does is allow arbitrary value assignments. As you go up a tree, you need to recalculate the value in each node, i. e. the minimum/maximum on the corresponding range. You can split this range into three: everything before the element you’re assigning, the element itself, and everything after. These ranges are extending away from the element you’re assigning, the further away the higher you are in the tree. This means you can compute them from the same two BITs.

    Let’s see an example. Take the trees illustrated in the paper, i. e. a pair of minimizing BITs on a data array of length 15. Let’s say we want to assign a new value to element 2.

    First we update element 2 itself in the raw data array. This is easy.

    Now we want to update the right-leaning tree, BIT1. We start at node 2 and go up the tree until we reach the root: so we go through nodes 2, 4 and 8. They correspond to ranges [1,2], [1,4] and [1,8]. We know the new value at index 2 (we’ve just assigned it!), so to update these nodes, we need to know the minima on ranges [1,1] and [3,2] (empty) for node 2, [1,1] and [3,4] for node 4, [1,1] and [3,8] for node 8.

    For [3,_], we start at 3 in BIT1 and climb up the tree, taking our values from the corresponding nodes in BIT2: at 3 we have the minimum on [3,3], at 4 we have the minimum on [4,7] for a total of [3,7], at 8 we have the minimum on [8,15] for a total of [3,15]. What we need though are the minima on [3,4] and [3,8]… but we can get those by adding the elements at indices 4 and 8 individually.

    [1,1] is a degenerate case, but in general we start at 1 in BIT2 and climb up the tree. Unlike the [3,_] case, we don’t need to add individual elements here.

    In total, we climb BIT1 once or twice depending on how you count to actually update it and to get the minima on [3,_], and we climb BIT2 once to get the minima on [_,1].

    We update BIT2 similarly.

    Some more examples:

    • To update element 4, we’ll need the minima on [1,3] and [5,8], and we’ll get them by climbing BIT2 from 3 to read [3,3] and [1,2] from BIT1, and by climbing BIT1 from 5 to read [5,5] and [6,7] from BIT2 and add 8 individually.

    • To update element 5, we’ll need the minima on [6,6] and [6,8], and we’ll get them by climbing BIT1 from 6 to read [6,7] from BIT2 and add 8 individually.

    • To update element 7, we’ll need the minimum on [5,6], and we’ll get it by climbing BIT2 from 6 to read [5,6] from BIT1.

    • If we imagine we actually have more than 15 elements, so element 16 actually exists in BIT1, then to update element 15, we’ll need the minimum on [1,14], and we’ll get it by climbing BIT2 from 14 to read [13,14], [9,12] and [1,8] from BIT1.

    • If we imagine we actually have more than 15 elements, so element 16 actually exists in BIT1, then to update element 8, we’ll need the minima on [1,7] and [9,16], and we’ll get them by climbing BIT2 from 7 to read [7,7], [5,6] and [1,4] from BIT1, and by climbing BIT1 from 9 to read [9,9], [10,11], [12,15] from BIT2 and add 16 individually.

    I hope this helps!

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Author of the paper here. I'm glad to see people interested in the topic. When I did the research for this back in 2011 there was only the recursive Segment Tree. I'm not sure when the iterative version appeared, but I'll definitely do some tests to see how it compares to this version :)

»
3 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

So I implemented this and compared it to a bottom-up segment tree implementation. The short verdict: this both uses more memory and is slower. Admittedly, my speed test wasn’t very rigorous, and I’d like to repeat it with more rigour, but the result is in line with my understanding of the theory.

Here’s a theoretical explanation of my observations: I need two BITs and an array of the raw data for a total of 3n values, versus 2n - 1 values for a single segment tree (which includes the raw data in its bottom row). The speed reduction is probably due to the randomly accessed memory locations being more spread out. And if we want to support arbitrary value assignments rather than only increments for a maximizing tree or decrements for a minimizing tree, then updates become even slower (the paper suggests a factor of three).

This alternative scheme on the ITMO wiki seems more promising. The text is in Russian only, sorry; but like the picture shows, if we essentially shift the second BIT by one data array element (note how the two BITs don’t overlap; compare to the trees shown in the above paper), we can get rid of the raw data array. Still, I expect that this will only reduce the memory usage back to 2n but not improve the speed enough. I haven’t tested this (yet).

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you , can you share your implementation?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Could you elaborate a bit(pun-intended)? Which one was slower, the bottom up or the BIT?

    When I learnt them, I found Segment Tree quite easy to comprehend, and the short implementation just gave it a bonus. I can't say the same about the BIT, even though it is short enough.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      The BITs were slower and consumed more memory. I’ll post my code and maybe run some more/better tests shortly.

      Generally, the BIT is great for invertible operations like sum and nonzero product (although hmm… I’m starting to doubt this), and it is completely awesome when your queries are always of the form [0, i] or always of the form [i, n] (where n is fixed but i can vary between queries).

      By the way, if you’re having trouble understanding how the BIT works, the pictures in the paper linked in this blog post might help. The numbers inside the circles are the indices, and the small numbers next to them are the values stored in the nodes. When we change a value, we propagate the change up the tree. When we want to know the sum/product on a range [0, i], we take the tree that has 0 as its root and walk up this tree, and take (add/multiply in) the value for each node that we pass from the other tree. Note that we don’t actually need to store the tree we’re walking on, as we don’t use any of its values here. If you’re interested in ranges of the form [i, n], walk up the other tree instead and store this one. The walking up and down either tree can be done with bitwise operations, namely, by adding or subtracting the last 1-bit in the index.

      But that’s a single BIT. Here the idea is to use two BITs simultaneously, one of the [0, i] form and the other of the [i, n] form (and additionally the raw data array), to handle arbitrary range requests [i, j], and it seems it doesn’t quite beat a bottom-up segment tree in any respect. The memory usage is higher, the speed is lower, and the code is longer and more complicated. Oh, and for arbitrary value assignments the algorithm becomes even more complicated and slower. It may still be faster than a recursive top-down segment tree though.