Can some one please suggest me some situations or usecases where we must opt BIT Tree and when to use segment Tree ? Also , please tell me why did they choose BIT Tree instead of using Segment tree in Number of elements greater than K in the range L to R using Fenwick Tree (Offline queries) - GeeksforGeeks problem
2 Likes
Here’s a link to help you learn more about Seg. trees and BITs. If you can solve a problem using BITs, you can solve it with Seg. trees as well. The time complexities for both are the same, but BITs are a tad bit quicker. Problem is, Seg. trees can do things that BITs can’t. In competitive coding I guess, you may solve most of such questions with Seg. trees alone. 
1 Like
Yes , it is true Segtree is more powerful than BIT but when to use them is tricky , you can’t use BIT everywhere as you can use segtree , there is one more condition that should always satisfy to implement BIT whereas not required in segtree that is , the operation must be reversible function , like we can do sum range , not range gcd . Also BIT is easier and faster , also faster to implement than segtree , it takes O(n) space .
1 Like
Here’s a really fast implementation of SegTree. It takes O(2*N) space .