How can I decide which, Segment tree or BIT to use in a particlar problem?
Thanks in advance.
2 Likes
Segment Tree or Binary Index Tree can be used in equal perspective.
Major hint from the problem statement where you are asked to Query within a range or a kind of.
refer below link for sample problem
Happy Coding :)
Below is the answer quoted from
https://www.quora.com/How-does-one-decide-when-to-use-a-Segment-Tree-or-Fenwick-Tree
Here are the things to keep in mind while deciding whether to use segment tree or binary indexed tree:
Anything that can be done using a BIT can also be done using a segment tree :
BIT stores cumulative quantities for certain intervals. Segment tree stores cumulative quantities for those intervals and more. In particular, if we are creating a data structure to deal with an array of size N=2^K, the BIT will have cumulative quantities for N intervals whereas the segment tree will have cumulative values for 2N-1 intervals
There are things that a segment tree can do but a BIT cannot :
A BIT essentially works with cumulative quantities. When the cumulative quantity for interval [i…j] is required, it is found as the difference between cumulative quantities for [1…j] and [1…i-1]. This works only because addition has an inverse operation. You cannot do this if the operation is non-invertible (such as max). On the other hand, every interval on a segment tree can be found as union of disjoint intervals and no inverse operation is required
A BIT requires only half as much memory as a segment tree : In cases where you have masochistic memory constraints, you are almost stuck with using a BIT
Though BIT and segment tree operations are both O(log(n)), the segment tree operations have a larger constant factor :
This should not matter for most cases. But once again, if you have masochistic time constraints, you might want to switch from a segment tree to a BIT. The constant factor might become more of a problem if the BIT/Segment tree is multidimensional.
With practice, coding either will be very fast :
If you have coded a segment tree 100 times, you will get it very fast the next time you do it. So no need to worry about code being long.
10 Likes
You won’t have a problem choosing because everything that can be done by a BIT can be done by a segment tree, but not the other way around. So if the quantities are not cumulative (they have certain specifications, not just adding), then most probably you have to use a segment tree.
A BIT was harder for me to visualize at first and then I got the hang of it, but understanding segment trees was pretty easy.
And don’t worry about the code being long, I made a article of a great short way of coding segment trees.
Have fun.
1 Like
Amazing implementation! I used the same array layout. but I did not use the bottom up update/query approach.
nice explanation.
Dont you think BIT requires 1/4 of memory as required by segment tree in worst case ?
What is meant by worst case here? Bit always requires O(n) memory and segment tree requires exactly 2*(2^ceil(log2(n)) memory if written in recursive manner, else 2*n if written in iterative manner (See http://codeforces.com/blog/entry/18051 ) But many a times, memory is not a constraint. If it was, the overall execution time will also increase with increase in “n”. So, again usage depends upon the problem and your practice with the data structure. I hope it is clear.