Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

By Animadversion, history, 2 years ago, ,

Hi everyone! All that you can do it with BIT can be done with segment tree?

•
• +11
•

 » 2 years ago, # |   +2 Yep
 » 2 years ago, # | ← Rev. 2 →   +19 Sometimes you can only get AC with Fenwick only (due to constant factor).
•  » » 2 years ago, # ^ |   +7 I had never learnt Fenwick and never ever had the need to implement one because I would always say that Segment tree is better, this post made me learn Fenwick in order to prove a point (or disprove).Problem to solve is given N numbers and 2 type of queries: type 0 means add r to lth number and type 1 means get sum from l to r inclusive.I tried random cases and extreme cases (Q=N=10^5) and segment treeIn my computer I get: 1000 Extreme cases: Total Segment tree: 14.434 Total Fenwick tree: 16.16210000 random cases: Total Segment tree: 21.677 Total Fenwick tree: 24.464In code forces custom run I get (had to run less tests because it gets timed out): 300 Extreme cases: Total Segment tree: 2.140 Total Fenwick tree: 1.4232000 random cases: Total Segment tree: 1.977 Total Fenwick tree: 1.446Basically results are inconsistent. So, which one is better I guess it depends, either way, differences are minimal to the point where I/O would actually have more impact than the data structure.My conclusion is Segment tree is better, simply because it can be easily modified to achieve other thing's which BIT doesn't seem to be able to.In order to learn segment tree I would recommend to start with recursive (to understand it), and then iterative (how to optimize it).My code: http://pastebin.com/fFRY5FQENote: I used the iterative implementation of segment tree, since obviously recursive is slower.
•  » » » 2 years ago, # ^ |   +8 I am sorry if I mislead anyone . I have never learnt about the iterative segment tree ( I am too lazy for it (Pun!) ). I was talking about recursive implementation of segment tree.
•  » » » 2 years ago, # ^ |   +5 Sometimes you are forced to use BIT due to memory limit, esp when the queries are now in 2D.I used to stick with segment tree but I have to use BIT for a 1000*1000 matrix query.
 » 2 years ago, # |   +1 Really thank you!
 » 2 years ago, # |   +9 Here you can find everything you need to know about BIT Vs Fenwick tree: https://discuss.codechef.com/questions/73815/segment-tree-vs-bit
•  » » 2 years ago, # ^ |   +45 Maybe BIT Vs Segment tree :)
 » 2 years ago, # |   0 Yes, haha! Wrote that in a hurry. :P
 » 2 years ago, # |   +5 BIT faster than segment tree . this submit http://codeforces.com/contest/703/submission/19672070 got TLE when i used segment tree , but when i used BIT it got AC http://codeforces.com/contest/703/submission/19672254
•  » » 9 months ago, # ^ |   0 Just change cin to scanf and the code gets AC. Modified Code : http://codeforces.com/contest/703/submission/36369065
 » 2 years ago, # |   0 I can't really think of anything than can be done with a BIT and can't be done with a Segment Tree. Although it may seem useless if you look at it this way, it is really handy when it can be used. BIT is easier and faster to code, and it uses a lot less memory. It also works slightly faster in most the cases I have tried both of them :)
 » 2 years ago, # | ← Rev. 2 →   +4 Spoj — DQUERYSpoj — RATINGMay these two problems help you to know time , effort and runtime difference between both trees !
 » 2 years ago, # | ← Rev. 2 →   0 Well, I have also never seen a problem where you can use only BIT. As said in comments above Fenwick Tree is very fast as compared to segment tree. Also, it uses less memory. But I still use segment tree most of the times.
•  » » 2 years ago, # ^ |   +16 The final sentence contradicted to the other :p
 » 2 years ago, # |   0 Actually, I think BIT lets you do multi-dimensional structures much more easily than traditional segment tree implementations.
•  » » 2 years ago, # ^ |   0 just like the old saying:"Segment Tree can do everything BIT can do and can't do." But sometimes it is very difficult to code.