Segment tree vs BIT

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.

19 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.