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

Do I need to learn Fenwick Tree when I already know how to use Segment Tree?
Автор nhphuc, 13 месяцев назад, По-английски

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.

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

»
13 месяцев назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

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

→ Ответить
»
13 месяцев назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    13 месяцев назад, # ^ |
      Проголосовать: нравится -10 Проголосовать: не нравится

    Refer to tourist's implementation here

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

    → Ответить
»
13 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
13 месяцев назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    13 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    → Ответить
»
13 месяцев назад, # |
← Rev. 2   Проголосовать: нравится +14 Проголосовать: не нравится

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.

→ Ответить