I like the Fenwick Tree by the simplicity of its implementation, but I am afraid that there are tasks with which it cannot cope, unlike the Segment Tree. Question: What can the Segment Tree do that the Fenwick Tree cannot?

    1 answer 1

    I will quote Vicky :

    Note that using the Fenwick tree for the maximum can not reduce the value recorded in the cell. If you want the data structure to have this capability, you should use a segment tree for the maximum.

    And also a post from Habr :

    Comparison (of the Fenwick tree) with the segment tree

    Benefits:
    - already mentioned simplicity and speed
    - memory takes O (N)

    Disadvantages:
    - the function must be reversible, which means that the tree cannot count the minimum and maximum (except for the cases when we can donate some data).

    • In fact, I will say more, the maximum in the Fenwick tree will be only from the beginning. It cannot be found on the internal sub-cutter. - pavel