nhphuc's blog

Do I need to learn Fenwick Tree when I already know how to use Segment Tree?
By nhphuc, 13 months ago, In English

I'm currently learning fenwick tree and I find it quite difficult (in my opinion, it's more difficult than segment tree). As far as I know, most problems that can be solved with a fenwick tree can also be solved with a segment tree. So, in addition to memory optimization and simple usage, is there anything more optimal about fenwick tree than segment tree? And, sure, can anyone give me websites to use to learn fenwick tree? Thank you.

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

Comments Comments (7)
| Write comment?
»
13 months ago, # |
  Vote: I like it +12 Vote: I do not like it

Yes. Because of the low constant it is often 5 times faster than the analogue segment tree.

https://cp-algorithms.com/data_structures/fenwick.html

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

It's way faster, it's not that hard once you've implemented it enough times. I find it very easy, honestly, you just need to remember the operation to move up/down on the tree.

→ Reply
  • »
    »
    13 months ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    Refer to tourist's implementation here

    I think it's simple and very clear (also 0-indexed, very nice).

    → Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

You can test it here and find out for yourself.

It depends on what you're trying to do, and decide if learning is worth it, or to spend your time on other things first, and come back later. I'd say it's ok to not learn it now, but it can come back to bite you later if you leave it for too long. I've gotten a few (but not often) timeouts with segment tree, so I only use fenwicks for strictly dynamic range sum problems now.

Learning algorithms isn't just learning how to solve its problem, it's learning how to construct the algorithm, and to use the same path to solve other problems with it. It's similar to learning Kuhn's and Hopcroft-Karp's for bipartite matching. You can use only the latter for application, but you won't know how to maintain a transversal matroid without the former.

Since you're Vietnamese, here is a good resource

→ Reply
»
13 months ago, # |
  Vote: I like it +12 Vote: I do not like it

most problems that can be solved with a fenwick tree can also be solved with a segment tree

I would go as far as saying that all such problems can be solved by segment trees. Fundamentally, a Fenwick tree is exactly half of a segment tree, as explained by this comment. So if you want to save a factor of 2 in memory usage, then Fenwick trees can be a good alternative. But my advice in general is to not bother with Fenwick trees and just stick to using segment trees for everything.

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

    I actually remember coming across one problem where segment tree's high constant factor caused TLE: 103055B - Restore Atlantis

    My solution's overall complexity came down to somewhere around O(C^2 log n). Since the problem had a tight time limit I ended up using Fenwick tree for the smaller constant factor.

    → Reply
»
13 months ago, # |
← Rev. 2   Vote: I like it +14 Vote: I do not like it

The novelty of Fenwick tree that really matters is not the constant factor; it is the representation of the tree that matters, and the idea behind the representation is sometimes used in problems as well.

The "interval definition" that maps an index to the previous index which flips the rightmost 1 bit (equivalently, the previous index divisible by the highest power of 2 that divides the current index) ends up giving it a tree structure (more precisely, an anti-arborescence structure, rooted at the 0-th index). You can do the same with any other tree structure on the array too, it is just that the particular Fenwick tree structure tends to be fast (though unusually cryptic) to code, as well as guarantees logarithmic depth.

Once you realize this, I believe that you can generalize this to structures on trees that can do things similar to this blog.

→ Reply