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
I am not getting how update operation is done.
Can you explain?
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!
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 :)
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).
Thank you , can you share your implementation?
Sure! Here’s my current code: https://gist.github.com/astiob/2d519167a2de9ee80dde
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.
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.