MazzForces's blog

By MazzForces, history, 8 years ago, In English

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

  • Vote: I like it
  • 0
  • Vote: I do not like it

8 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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: The running time is .10 which is better than many other solutions using BIT.

3> Yes, segment tree can usually do much more.