Fenwick Tree / BIT (Conceptual)

A Fenwick Tree, or Binary Indexed Tree (BIT), is a data structure that supports:

  • Prefix sum queries: sum[0..i].
  • Point updates: add a value to a[i].

Both in O(log n) time, with a simple implementation and O(n) space. It is a specialized, lighter alternative to a full segment tree for sum‑like operations.

High-Level Idea

The BIT uses an array bit[1..n] (1‑based indexing) where each index i is responsible for a range of elements determined by the least significant bit (LSB) of i.

  • LSB(i) = i & -i.
  • bit[i] stores the sum of elements in the range (i - LSB(i) + 1 .. i].

This clever encoding lets us:

  • Query prefix sums by traversing indices downward using i -= LSB(i).
  • Update a position by traversing indices upward using i += LSB(i).

Operations

Assume n elements and 1‑based indexing.

Update: add delta to a[i]:

Java
void add(int i, int delta) {
    while (i <= n) {
        bit[i] += delta;
        i += i & -i; // move to next responsible index
    }
}

Prefix sum: sum of a[1..i]:

Java
int sum(int i) {
    int res = 0;
    while (i > 0) {
        res += bit[i];
        i -= i & -i; // move to parent index
    }
    return res;
}

Range sum [L, R] can be computed as sum(R) - sum(L-1).

When to Use a BIT vs Segment Tree

Use a BIT when:

  • You only need:
    • Prefix sums / range sums.
    • Point updates.
  • You want a compact and simple implementation.

Use a segment tree when:

  • You need more general range aggregates (min, max, gcd, etc.).
  • You need range updates with lazy propagation.

Both structures provide O(log n) queries and updates, but BITs are often easier to code and have lower constants for prefix sums.

Practice Tips

  • Get comfortable with the i & -i trick and how it relates to binary representation.
  • Implement BIT in both iterative and wrapper‑function styles.
  • Practice using BIT for:
    • Prefix sums.
    • Counting inversions.
    • Online frequency statistics.

Once you internalize BIT operations, many “prefix sum + updates” problems become straightforward.