Animadversion's blog

BIT vs Segmen Tree
By Animadversion, history, 8 years ago, In English

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

  • Vote: I like it
  • +11
  • Vote: I do not like it

Comments Comments (16)
| Write comment?
»
8 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Yep

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +19 Vote: I do not like it

Sometimes you can only get AC with Fenwick only (due to constant factor).

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    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 tree

    In my computer I get:
    1000 Extreme cases:
    Total Segment tree: 14.434
    Total Fenwick tree: 16.162

    10000 random cases:
    Total Segment tree: 21.677
    Total Fenwick tree: 24.464

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

    2000 random cases:
    Total Segment tree: 1.977
    Total Fenwick tree: 1.446

    Basically 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/fFRY5FQE

    Note: I used the iterative implementation of segment tree, since obviously recursive is slower.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      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.

      → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      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.

      → Reply
»
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Really thank you!

→ Reply
»
8 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Here you can find everything you need to know about BIT Vs Fenwick tree: https://discuss.codechef.com/questions/73815/segment-tree-vs-bit

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Yes, haha! Wrote that in a hurry. :P

→ Reply
»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

BIT faster than segment tree . this submit http://mirror.codeforces.com/contest/703/submission/19672070 got TLE when i used segment tree , but when i used BIT it got AC http://mirror.codeforces.com/contest/703/submission/19672254

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 :)

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

Spoj — DQUERY

Spoj — RATING

May these two problems help you to know time , effort and runtime difference between both trees !

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

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.

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Actually, I think BIT lets you do multi-dimensional structures much more easily than traditional segment tree implementations.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply