Binary Indexed Tree (Fenwick)

Point Update, Prefix Query

update(i, delta): add delta to index i. Propagate by adding the lowest set bit to the index. query(i): sum from 1 to i. Accumulate by removing the lowest set bit from the index. Both O(log n).

O(log n) per op

O(n)

How It Works

A Fenwick tree (binary indexed tree) stores partial sums in a flat array where the index's binary representation encodes responsibility: entry i covers the lowbit(i) = i & (-i) elements ending at position i. A prefix-sum query walks downward, repeatedly stripping the lowest set bit (i -= i & (-i)) and accumulating the covered blocks — at most one block per bit, so O(log n). A point update walks upward, adding the delta to every responsible entry via i += i & (-i), also O(log n).

The result matches a segment tree's O(log n) point-update/prefix-query bounds in a fraction of the code — about ten lines — with exactly n+1 array slots and excellent cache behavior. Arbitrary range sums come from two prefix queries: sum(L, R) = query(R) - query(L-1). BITs are 1-indexed by construction, and forgetting that offset is the classic implementation slip.

Step-by-Step Visualization

BIT: efficient prefix sums with point updates

i & (-i)Lowest set bit trick

1/3

Code

Java

class BIT {
  int[] tree;

  BIT(int n) { tree = new int[n + 1]; }

  void update(int i, int delta) {
    for (; i < tree.length; i += i & (-i))
      tree[i] += delta;
  }

  int query(int i) {
    int sum = 0;
    for (; i > 0; i -= i & (-i)) sum += tree[i];
    return sum;
  }

  int rangeQuery(int l, int r) { return query(r) - query(l - 1); }
}

Tips & Gotchas

1Binary Indexed Tree (Fenwick Tree) for prefix sum queries

2update(i, delta): add delta at index i, propagate up

3query(i): sum from 1 to i, iterate down using lowest set bit

Practice Problems

1Range Sum Query - Mutable
2Count of Smaller Numbers After Self
3Reverse Pairs
4Queries on a Permutation With Key

About the Binary Indexed Tree (Fenwick) Pattern

A simpler alternative to segment trees for prefix sum queries. Uses bit manipulation on indices to determine parent-child relationships. Much less code than a segment tree, but limited to prefix-based operations.

Key insight

If you only need prefix queries with point updates, use a BIT (simpler). If you need arbitrary range queries + range updates, use a segment tree with lazy propagation. Sparse table is O(1) query but static.

Common Range Structures Interview Problems

Range Sum Query - Mutable
Count of Smaller Numbers After Self
Range Minimum Query
Longest Increasing Subsequence (BIT approach)

Frequently Asked Questions

When is a BIT preferable to a full segment tree?

Whenever the operation is invertible and prefix-decomposable — sums, counts, XOR — and updates are point updates. The BIT delivers the same O(log n) bounds with far less code and memory. Reach for a segment tree when you need range min/max (not invertible), lazy range updates, or complex merged aggregates.

What exactly does i & (-i) do in the traversal loops?

It isolates the lowest set bit of i via two's complement. Subtracting it during queries jumps to the previous non-overlapping block, so a prefix sum touches one block per set bit of the index; adding it during updates jumps to the next entry whose range contains position i.

How do BITs solve counting problems like Count of Smaller Numbers After Self?

Index the BIT by value (after coordinate compression), iterate the array right to left, and for each element query the count of values smaller than it already inserted, then insert it. Every step is O(log n), turning an O(n^2) pairwise count into O(n log n).