Segment Tree vs Fenwick Tree
A Fenwick tree if you only need prefix sums with point updates, because it is a fraction of the code and uses less memory. A segment tree for anything else: minimums, maximums, range updates, or any operation that does not decompose into prefixes.
Both give O(log n) updates and queries over an array, and for prefix sums they do the same job. The Fenwick tree is dramatically smaller: one array, two loops of three lines each, and no recursion. The segment tree is more code and more memory, and it can do things the Fenwick tree fundamentally cannot.
Side by side
| Dimension | Segment Tree | Fenwick Tree |
|---|---|---|
| Query and update | O(log n) | O(log n) |
| Memory | 4n, for a safe tree layout | n plus 1 |
| Code size | Substantially more | About ten lines |
| Sum queries | Yes | Yes |
| Min or max queries | Yes | No, they do not decompose into prefixes |
| Range updates | Yes, with lazy propagation | Only via a difference-array trick |
| Constant factor | Higher | Lower, the loops are tiny |
When to pick each
Segment Tree
- The operation is a minimum, a maximum, or a greatest common divisor, where a prefix decomposition does not exist.
- You need range updates as well as range queries, which lazy propagation handles.
- Each node needs to store something richer than a number, such as a sorted list in a merge sort tree.
Fenwick Tree
- Prefix sums with point updates, which is the case it was designed for.
- Memory is tight, since it needs one array rather than four times the input.
- You are writing under time pressure and want the shortest correct thing.
Trying to use a Fenwick tree for range minimum queries. It looks like it should work, and it does not: subtracting a prefix from a prefix is meaningful for sums and meaningless for minimums, because you cannot remove an element's contribution from a minimum once other values are involved. Range minimum with updates needs a segment tree; range minimum without updates can use a sparse table for O(1) queries.
Questions people ask
Why is the Fenwick tree array n plus 1?
It is one-indexed, because the whole structure relies on isolating the lowest set bit, and index zero has none. Slot zero is left unused rather than special-cased.
Can a Fenwick tree do range updates?
For point queries, yes, by storing differences and updating two positions. For range updates with range queries you need two Fenwick trees and some care, at which point a lazy segment tree is usually the clearer choice.
What about a sparse table?
It answers minimum queries in O(1) rather than O(log n), but it cannot handle updates at all, since one changed element invalidates every block containing it. Use it for static data, and a segment tree when the array changes.