Fenwick Trees

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

Reach for a Fenwick when you need prefix sums, point updates, or range sums and want minimal code and memory. Reach for a segment tree when you need arbitrary range aggregates (min/max/gcd), range updates with lazy propagation, 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. Solve: range-sum-with-updates and offline 2D point problems.

When It’s the Right Tool