← System Design Simulator

Fenwick (BIT) Visualization for Coding Interviews

By Rahul Kumar · Senior Software Engineer · Updated · Category: Trees

Low-bit trick for prefix-sum updates/queries in O(log n).

Concept

A Fenwick tree, also called a Binary Indexed Tree (BIT), is a minimalist data structure that answers prefix-sum queries and point updates in O(log n) time using just an n+1 sized array. Peter Fenwick's trick from 1994 is to let the binary representation of each index describe which range of the underlying array that slot is responsible for: index i covers a range of length equal to i's lowest set bit (i & -i). That encoding lets you walk both queries and updates as sequences of lowbit additions and subtractions, touching at most log n slots on each pass. Fenwick trees are the fastest and simplest choice whenever the aggregation is invertible - sum, xor, complex products - and you only need prefix or range-sum answers. They lose to segment trees for non-invertible aggregates like min or max, but they are roughly half the code, half the memory, and twice the constant-factor speed for the problems they do solve. Expect to see them in inversion counting, online order statistics, and range-update-point-query variants.

Fenwick (BIT) — Interactive Simulator

Runs fully client-side in your browser; no sign-up. Or open full screen →

Launch the interactive Fenwick (BIT) visualization — animated algorithm, step-through, and live data-structure updates.

How it works

Index each BIT slot by its responsibility: slot i is responsible for the range (i - lowbit(i), i], where lowbit(i) = i & -i is the value of the lowest set bit. For i = 12 (binary 1100), lowbit is 4, so BIT[12] stores the sum of the original array's entries at positions 9 through 12. Prefix sum up to index i walks DOWN the BIT: start at i, add BIT[i] to the running total, subtract the lowbit (i -= i & -i), and repeat until i becomes 0. Because each subtraction clears exactly the lowest set bit, the walk touches at most popcount(i) <= log n slots, and the ranges those slots cover partition [1, i] exactly. Update at index i walks UP the BIT: add the delta to BIT[i], add the lowbit (i += i & -i), and repeat until i exceeds n. Each addition either flips a low bit upward or carries into a higher bit, so you visit at most log n slots, and every slot whose range covers position i is guaranteed to be hit. Range sum [l, r] is just prefixSum(r) - prefixSum(l-1), which is why the structure only works for invertible aggregates. A two-BIT trick extends this to range-update-range-query in O(log n) per op.

Implementation

Fenwick tree (BIT) with update, prefixSum, and range sum
public class FenwickTree {
    private final int n;
    private final long[] bit;

    public FenwickTree(int n) {
        if (n <= 0) throw new IllegalArgumentException("n must be positive");
        this.n = n;
        this.bit = new long[n + 1]; // 1-indexed
    }

    public FenwickTree(int[] input) {
        this(input.length);
        for (int i = 0; i < input.length; i++) update(i + 1, input[i]);
    }

    /** Add delta to position i (1-indexed). */
    public void update(int i, long delta) {
        if (i <= 0 || i > n) throw new IndexOutOfBoundsException();
        // walk UP: i += i & -i
        for (; i <= n; i += i & -i) {
            bit[i] += delta;
        }
    }

    /** Sum of positions [1..i] (1-indexed, inclusive). */
    public long prefixSum(int i) {
        if (i < 0 || i > n) throw new IndexOutOfBoundsException();
        long sum = 0L;
        // walk DOWN: i -= i & -i
        for (; i > 0; i -= i & -i) {
            sum += bit[i];
        }
        return sum;
    }

    /** Sum of positions [l..r] (1-indexed, inclusive). */
    public long rangeSum(int l, int r) {
        if (l > r) throw new IllegalArgumentException("l must be <= r");
        return prefixSum(r) - prefixSum(l - 1);
    }

    /** Smallest index i such that prefixSum(i) >= target (for positive values). */
    public int lowerBound(long target) {
        int pos = 0;
        int log = Integer.highestOneBit(n);
        for (int k = log; k > 0; k >>>= 1) {
            int next = pos + k;
            if (next <= n && bit[next] < target) {
                pos = next;
                target -= bit[next];
            }
        }
        return pos + 1;
    }
}

Complexity

Common pitfalls

Key design decisions & trade-offs

Practice problems

Interview follow-ups

Why it matters

Fenwick (BIT) is a core part of the Trees toolkit. If you are preparing for a technical interview at a top-tier company or teaching a course, a working visualization is the fastest path from "I read about it" to "I understand it".

Related