Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

Fenwick trees: update points and query prefix totals

Last updated: 5 Oct 20269 min read
tutorial
IntermediateBy AITrove Editorial

A Fenwick tree stores selected partial sums in a one-indexed array. Adding a delta at one position walks upward using the least significant set bit; querying a prefix walks downward using the same bit rule. Both operations cost O(log n) time and the structure uses O(n) space. A half-open range sum [left, right) is prefix(right) minus prefix(left). This is useful when values change between queries; a static prefix-sum table is simpler and faster per query when updates never occur. The index conversion between zero-based application positions and one-based internal positions must be explicit.

Operational case

A depot tracks four daily counts: 47, 31, 26, and 58. The sum for days [1, 4) is 115. A late batch adds 3 to day index 2, so the same range becomes 118 without rebuilding all cumulative totals. The update is a delta, not a replacement value. A negative delta can correct an overcount, but the caller must determine whether negative final daily counts are valid for its business contract. The data structure handles arithmetic; it does not validate the meaning of a correction.

Working Python program

python
daily_scans = [47, 31, 26, 58]
fenwick = [0] * (len(daily_scans) + 1)

def add(day_index, delta):
    position = day_index + 1
    while position < len(fenwick):
        fenwick[position] += delta
        position += position & -position

def prefix(end_exclusive):
    total = 0
    while end_exclusive:
        total += fenwick[end_exclusive]
        end_exclusive -= end_exclusive & -end_exclusive
    return total

for day_index, scan_count in enumerate(daily_scans):
    add(day_index, scan_count)
print(prefix(4) - prefix(1))
add(2, 3)
print(prefix(4) - prefix(1))

Output

Output
115
118

Time, space, and tradeoff

The shown build uses n updates and costs O(n log n); a specialized linear construction can do O(n). Each later point update and prefix query costs O(log n), with O(n) stored numbers. Validate 0 <= day_index < n and 0 <= end_exclusive <= n in a public API. Passing an invalid negative index into bit arithmetic can make a loop fail to progress. If the operation changes from sum to minimum, this additive update formula no longer applies directly.

Common Mistakes

  • Do not pass a replacement value where the method expects a delta.
  • Do not mix zero-based input positions with one-based internal indices.
  • Do not reuse the sum implementation for arbitrary noninvertible operations.

Connected lessons

Heavy-light decomposition: sum weights along a tree path adds a related operation contract.

Two-dimensional Fenwick tree: update cells and sum rectangles adds a related operation contract.

Two Fenwick trees: add across ranges and query sums adds a related operation contract.

Square-root blocks: update one capacity and sum a range extends this range-query decision.

Coordinate compression: preserve order with dense integer ranks extends this operation choice.

data structures
range-query-structures
Storage details