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
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.
23 Likes
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.
1 Like