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.

The 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)

Tiny worked example

Suppose you need many updates and prefix sums over an array.
In a Fenwick tree, index `i` stores a sum covering the last `lowbit(i)` positions ending at `i`.
To query `prefix(r)`, keep adding tree values and move `r` downward by `lowbit(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 & -x` isolates the lowest set bit, not the highest one.

How to recognize this kind of problem

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.