Блог пользователя Animadversion

Автор Animadversion, история, 8 лет назад, По-английски

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

  • Проголосовать: нравится
  • +11
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Yep

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +19 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +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 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.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +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.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +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.

»
8 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Really thank you!

»
8 лет назад, # |
  Проголосовать: нравится +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

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится 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 :)

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

Spoj — DQUERY

Spoj — RATING

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

»
8 лет назад, # |
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.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 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.