Segement Tress and Binary Indexed Trees..

Revision en1, by MazzForces, 2016-01-11 15:09:52

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

Tags segment tree, binary indexed tree

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English MazzForces 2016-01-11 15:09:52 825 Initial revision (published)