Algorithms / Fenwick Tree Prefix Sum
Least You Need to Know: Fenwick Trees, Prefix Sums, and Low-Bit Jumps
Fenwick trees support prefix-sum queries and point updates in O(log n) by storing carefully chosen partial sums. The key bit trick is the low bit, which tells how large a range each index is responsible for.
Least you need to know
- Fenwick trees are commonly implemented with 1-based indexing.
- Each tree index stores a partial sum for a range determined by its lowest set bit.
- Prefix-sum queries move downward by subtracting the low bit.
- A range sum can be computed from two prefix sums.
- Fenwick trees trade a little bit arithmetic for compact
O(log n)operations.
Key notation
- lowbit(x) = x & -x — size of the segment represented at index x
- prefix(r) — sum of positions 1 through r
- range(l, r) — prefix(r) - prefix(l - 1)
Worked example
- Suppose you need many updates and prefix sums over an array.
- In a Fenwick tree, index
istores a sum covering the lastlowbit(i)positions ending ati. - To query
prefix(r), keep adding tree values and moverdownward bylowbit(r). - The path length is logarithmic because each step removes the lowest set bit.
Common mistakes
- Students often mix 0-based array indices with the 1-based Fenwick convention.
- Fenwick trees answer prefix sums directly; general range sums come from prefix differences.
x & -xisolates the lowest set bit, not the highest one.
How to recognize it
- The task needs many point updates plus prefix or range frequency/sum queries.
- The prompt is friendly to coordinate compression plus prefix counts.
- A full segment tree would work, but a lighter-weight prefix structure is enough.
Next recommended lesson
Continue through this topic with Least You Need to Know: Cycle Detection in Directed and Undirected Graphs.
Least You Need to Know: Cycle Detection in Directed and Undirected GraphsRelated lessons
Keep going with nearby lessons in the same topic.