Hello friends.. For the Past few Days I have been studying about Segment Trees and Binary Indexed Trees. I have noticed a few subtle differences among them ..I'm listing them below..Please let me know if I've gone wrong somewhere..
1> Binary Indexed Trees can be used for range queries when the array size is huge..>2*10^7 and above whereas segment trees can't be used for the same... 2> Binary Indexed Trees are more efficient for point sum/point update type of sums..Eg https://www.codechef.com/problems/SPREAD .I could't solve this problem using a segment tree with fast I/O with lazy prop..but with BIT I got AC... 3>Segment Trees can be used for a wider variety of problems such as RMQ, Sum, Square Sum, Frequency Table etc.
-Please comment....
http://ioinformatics.org/oi/pdf/v9_2015_39_44.pdf
1> Segment trees use O(N) space, same as BITs. The difference is that with segment tree you require at least an array of size 2*N and with a BIT you need an array of size N.
2> Depends on the implementation, a segment tree can be almost as fast as a BIT. Also, in this problem lazy propagation is not required since you are doing range updates and point queries. Here is an AC solution for the problem using segment trees: https://www.codechef.com/viewsolution/9163745. The running time is .10 which is better than many other solutions using BIT.
3> Yes, segment tree can usually do much more.