The Fenwick tree (Binary Indexed Tree / BIT) answers prefix sums and applies point updates in O(log n) using a single array of size n+1. It is the elegant, low-constant cousin of the segment tree.

The lowbit Trick

Every index i “owns” responsibility for the range ending at i:

lowbit(i) = i & (−i)          # least significant set bit
bit[i] = sum of arr[i − lowbit(i) + 1 .. i]

For example, lowbit(6) = 2, so bit[6] stores arr[5] + arr[6]. Because each range ends at its index and starts one past its lowbit boundary, the intervals tile the array without gaps or overlaps.

Build and Update — Walk Up

Adding delta at index i touches every ancestor that owns a range covering i:

add(i, delta):
  while i <= n:
    bit[i] += delta
    i += lowbit(i)      # next ancestor

With 1-indexed arr, building is for i in 1..n: add(i, arr[i]) — O(n).

Prefix Query — Walk Down

The prefix sum to index p peels off the ranges from right to left:

prefix(p):
  sum = 0
  while p > 0:
    sum += bit[p]
    p -= lowbit(p)      # jump to next non-overlapping range
  return sum

A range sum is prefix(r) − prefix(l−1). Both directions touch at most log₂(n) nodes — hence O(log n) with a tiny constant and zero extra storage beyond the array itself.

Fenwick vs. Segment Tree

Range Updates with Two BITs

A single BIT natively does point update + range query (add(i, v), then prefix(r) − prefix(l−1)). To support the opposite shape — range update + point query — apply a difference array on top of the BIT: add(l, v) and add(r+1, −v) turn “add v to [l, r]” into two point updates, and a point query is just prefix(i) over the difference tree.

To support the full range update + range query, keep two BITs, B1 and B2:

• range_add(l, r, v): B1.add(l, v), B1.add(r+1, −v), B2.add(l, v·(l−1)), B2.add(r+1, −v·r).
• prefix_sum(p): B1.prefix(p)·p − B2.prefix(p).
• range_sum(l, r): prefix_sum(r) − prefix_sum(l−1).

Every operation stays O(log n), and the two-BIT BIT outperforms a lazy segment tree on pure sum workloads — the segment tree still wins for arbitrary aggregates (min/max/gcd) or non-commutative operations, where the difference-array trick cannot be generalized. The table’s “No (native)” is only true for the single-BIT form; a pair of BITs removes that limitation entirely.

Reach for a Fenwick when you need prefix sums, point updates, range sums, or range updates over sums and want minimal code and memory. Reach for a segment tree when you need arbitrary range aggregates (min/max/gcd), lazy range updates over those aggregates, or non-commutative operations.

Practice Trajectory

1. Implement add and prefix; verify bit[8] equals the total sum.
2. Build the tree in O(n log n), then again in O(n) by accumulating into ancestors directly.
3. Count inversions in O(n log n): sweep, add(a[i], 1), query i − prefix(a[i]).
4. Implement order statistics: binary search the smallest index whose prefix ≥ k.
5. Implement range update + range query with two BITs and verify against a brute-force oracle on random data.
6. Solve: range-sum-with-updates and offline 2D point problems.

When It’s the Right Tool