Fenwick Trees (Binary Indexed Trees)

You have an array of 100,000 integers. Queries arrive asking “what’s the sum from index L to index R?” — and between queries, individual elements change. How do you handle both operations efficiently?

A plain array gives you O(1) updates but O(n) queries. A prefix sum array flips that: O(1) queries but O(n) updates to rebuild. Neither works when you’re hit with hundreds of thousands of both operations. You need O(log n) for both — and a Fenwick Tree delivers exactly that with astonishingly little code.

The Core Insight: Lowest Set Bit

Every positive integer has a binary representation, and every binary representation has a lowest set bit. The expression i & (-i) isolates that bit — this is the engine that drives the entire Fenwick Tree.

Index (decimal)  →  Binary  →  i & (-i)  →  Responsibility Range
       1             0001        0001 (1)     [1, 1]  — covers 1 element
       2             0010        0010 (2)     [1, 2]  — covers 2 elements
       3             0011        0001 (1)     [3, 3]  — covers 1 element
       4             0100        0100 (4)     [1, 4]  — covers 4 elements
       5             0101        0001 (1)     [5, 5]  — covers 1 element
       6             0110        0010 (2)     [5, 6]  — covers 2 elements
       7             0111        0001 (1)     [7, 7]  — covers 1 element
       8             1000        1000 (8)     [1, 8]  — covers 8 elements

The value i & (-i) — often called lowbit(i) — tells you how many elements index i is responsible for. Index 6 (binary 0110) has lowbit 2, so tree[6] stores the sum of 2 elements: arr[5] + arr[6]. Index 4 (binary 0100) has lowbit 4, so tree[4] stores the sum of 4 elements: arr[1] + arr[2] + arr[3] + arr[4].

Why 1-Based Indexing Matters

Fenwick Trees use 1-based indexing because 0 & (-0) = 0 — the bit trick breaks at zero. The lowest set bit of zero is undefined, and traversal loops would never terminate. Every Fenwick Tree implementation allocates an array of size n + 1 and ignores index 0.

The Fenwick Tree Structure

Here’s an ASCII diagram showing which ranges each tree index covers for an 8-element array:

tree[8] ─────────────────────────────── covers [1..8]
tree[4] ─────────────────┐              covers [1..4]
tree[2] ────────┐        │              covers [1..2]
tree[1] ──┐     │        │              covers [1..1]
          │     │        │
tree[3] ──┼──┐  │        │              covers [3..3]
          │  │  │        │
tree[6] ──┼──┼──┼──┐     │              covers [5..6]
tree[5] ──┼──┼──┼──┼──┐  │              covers [5..5]
          │  │  │  │  │  │
tree[7] ──┼──┼──┼──┼──┼──┼──┐           covers [7..7]
          │  │  │  │  │  │  │
arr:     [1] [2] [3] [4] [5] [6] [7] [8]

Each tree[i] stores the sum of lowbit(i) elements ending at position i. This partial-sum layout is what enables logarithmic traversal in both directions.

Operations

Prefix Query: Sum of Elements [1..i]

To compute the prefix sum up to index i, you accumulate tree[i], then strip the lowest set bit to jump to the next responsibility region, and repeat until i reaches 0.

int query(int i) {
    int sum = 0;
    while (i > 0) {
        sum += tree[i];
        i -= i & (-i); // strip lowest set bit
    }
    return sum;
}

Trace for query(7):

• i = 7 (binary 0111): add tree[7], strip lowbit → i = 6
• i = 6 (binary 0110): add tree[6], strip lowbit → i = 4
• i = 4 (binary 0100): add tree[4], strip lowbit → i = 0
• Done. Result = tree[7] + tree[6] + tree[4] = arr[7] + (arr[5]+arr[6]) + (arr[1]+arr[2]+arr[3]+arr[4]) = sum of all 7 elements. ✓

Each iteration removes at least one set bit from i, so the loop runs at most O(log n) times.

Point Update: Add Delta at Position i

To add a value delta to position i, you update tree[i], then add the lowest set bit to jump to the next ancestor that includes position i, and repeat until you exceed n.

void update(int i, int delta) {
    while (i <= n) {
        tree[i] += delta;
        i += i & (-i); // move to parent
    }
}

Trace for update(3, +5):

• i = 3 (binary 0011): update tree[3], add lowbit → i = 4
• i = 4 (binary 0100): update tree[4], add lowbit → i = 8
• i = 8 (binary 1000): update tree[8], add lowbit → i = 16
• i = 16 > n: done.

This updates every tree node whose responsibility range includes position 3. Again, O(log n) iterations.

Range Sum Query

Once you have query(i), computing any range sum is straightforward:

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

Sum of [l..r] = prefix sum up to r minus prefix sum up to l - 1. Two O(log n) calls = O(log n) total.

Building from an Array

Method 1: Repeated Updates — O(n log n)

The straightforward approach: start with a zeroed tree, then call update(i, arr[i]) for each element.

static FenwickTree buildSlow(int[] arr) {
    var ft = new FenwickTree(arr.length);
    for (int i = 0; i < arr.length; i++) {
        ft.update(i + 1, arr[i]); // 1-based indexing
    }
    return ft;
}

This performs n updates at O(log n) each — O(n log n) total.

Method 2: Forward Propagation — O(n)

A smarter approach: copy the array into the tree, then propagate each index’s value forward to its parent.

static FenwickTree buildFast(int[] arr) {
    int n = arr.length;
    var ft = new FenwickTree(n);
    // Copy values (1-based)
    for (int i = 0; i < n; i++) {
        ft.tree[i + 1] = arr[i];
    }
    // Propagate to parent
    for (int i = 1; i <= n; i++) {
        int parent = i + (i & (-i));
        if (parent <= n) {
            ft.tree[parent] += ft.tree[i];
        }
    }
    return ft;
}

Each element propagates once to its direct parent — O(n) total. Use this construction method when you have the full array upfront.

Complete Implementation

public class FenwickTree {
    private final int[] tree;
    private final int n;

    public FenwickTree(int n) {
        this.n = n;
        this.tree = new int[n + 1]; // 1-based indexing
    }

    /** Build from existing array in O(n). */
    public FenwickTree(int[] arr) {
        this.n = arr.length;
        this.tree = new int[n + 1];
        for (int i = 0; i < n; i++) {
            tree[i + 1] = arr[i];
        }
        for (int i = 1; i <= n; i++) {
            int parent = i + (i & (-i));
            if (parent <= n) {
                tree[parent] += tree[i];
            }
        }
    }

    /** Add delta to position i (1-based). */
    public void update(int i, int delta) {
        while (i <= n) {
            tree[i] += delta;
            i += i & (-i);
        }
    }

    /** Prefix sum [1..i]. */
    public int query(int i) {
        int sum = 0;
        while (i > 0) {
            sum += tree[i];
            i -= i & (-i);
        }
        return sum;
    }

    /** Range sum [l..r] (1-based, inclusive). */
    public int rangeQuery(int l, int r) {
        return query(r) - query(l - 1);
    }
}

Notice the entire data structure fits in under 40 lines. That’s one of the Fenwick Tree’s greatest strengths — you can write it from memory during an interview.

2D Fenwick Tree

For 2D prefix sum queries with updates (e.g., “sum of all elements in a sub-rectangle”), extend both loops to traverse two dimensions:

public class FenwickTree2D {
    private final int[][] tree;
    private final int rows, cols;

    public FenwickTree2D(int rows, int cols) {
        this.rows = rows;
        this.cols = cols;
        this.tree = new int[rows + 1][cols + 1];
    }

    public void update(int r, int c, int delta) {
        for (int i = r; i <= rows; i += i & (-i)) {
            for (int j = c; j <= cols; j += j & (-j)) {
                tree[i][j] += delta;
            }
        }
    }

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

    public int rangeQuery(int r1, int c1, int r2, int c2) {
        return query(r2, c2) - query(r1 - 1, c2)
             - query(r2, c1 - 1) + query(r1 - 1, c1 - 1);
    }
}

The 2D version applies inclusion-exclusion for rectangular range queries. Each operation runs in O(log(rows) × log(cols)).

Classic Interview Problems

Range Sum Query — Mutable

Problem: Given an integer array, handle two operations: update(i, val) — set element at index i to val, and sumRange(l, r) — return sum of elements from l to r.

Approach: Store the original array alongside the Fenwick Tree. On update(i, val), compute delta = val - arr[i], update the original array, then call ft.update(i + 1, delta). On sumRange, call ft.rangeQuery(l + 1, r + 1).

Count of Smaller Numbers After Self

Problem: Given an array nums, return an array counts where counts[i] is the number of elements to the right of nums[i] that are smaller than nums[i].

Approach:

1. Coordinate compression — map values to ranks [1..k] where k is the number of distinct values.
2. Traverse the array right to left.
3. For each element with rank r, query ft.query(r - 1) to count elements with smaller rank already inserted.
4. Then ft.update(r, 1) to register this element.

The Fenwick Tree acts as a frequency counter over compressed coordinates.

Reverse Pairs

Problem: Count pairs (i, j) where i < j and nums[i] > 2 * nums[j].

Approach: Similar to the above — coordinate compress the values and their doubled counterparts. Traverse right to left, querying and updating the BIT to count qualifying pairs. Alternatively, use a modified merge sort, but the BIT approach demonstrates the structure’s versatility.

Fenwick Tree vs. Segment Tree

Aspect	Fenwick Tree	Segment Tree
Code complexity	~30 lines	~80–120 lines
Memory	n + 1	4n (or 2n with iterative)
Constant factor	Faster (simple array access)	Slower (tree traversal overhead)
Operations supported	Invertible only (sum, XOR)	Any associative (min, max, GCD)
Lazy propagation	Not naturally supported	Full support
Range update + range query	Possible with 2 BITs	Cleaner with lazy propagation

The decision rule: If the operation is invertible (you can “undo” it — like subtraction undoes addition), reach for a Fenwick Tree. If you need min, max, GCD, or lazy propagation, use a Segment Tree.

Edge Cases and Interviewer Tips

Edge cases to handle:

• Array of size 0 or 1 — the tree still works, but verify boundary behavior.
• All elements identical — prefix sums grow linearly; no special treatment needed.
• Negative values — Fenwick Trees handle them naturally since addition is the core operation.
• Integer overflow — for large arrays with large values, use long[] instead of int[].

What interviewers want to hear:

• Explain why i & (-i) works — it’s two’s complement arithmetic. -i flips all bits and adds 1, so AND-ing with i isolates the single lowest set bit.
• Articulate the trade-off with Segment Trees clearly. Don’t claim one is universally better.
• Mention the O(n) construction method — it demonstrates deeper understanding than the naive O(n log n) build.
• If asked “can you do range updates with a Fenwick Tree?” — yes, using a difference array technique with two BITs, you can support both range updates and range queries. Describe the idea even if you don’t code it fully.

Time complexity summary:

• Point update: O(log n)
• Prefix query: O(log n)
• Range query: O(log n)
• Construction: O(n) optimal, O(n log n) naive
• Space: O(n)

The Fenwick Tree is a structure that rewards memorization. Its small code footprint means you can write it confidently and quickly, leaving more interview time for the actual problem-solving.