Introduction to Binary Indexed Tree Pattern

A Binary Indexed Tree (BIT / Fenwick Tree) makes prefix sums mutable by storing each index's cumulative contribution in a compressed forest of ranges, sized by the lowest set bit of the index, so that both update and prefixSum only ever touch O(log n) of those ranges instead of O(n) raw elements.

Recognize the pattern

• Array is mutable (point updates) and you need repeated prefix/range sum queries interleaved with updates.
• Keywords: "range sum query, mutable", "count of smaller elements after self", "inversion count", "count of elements ≤ x seen so far" (BIT-over-values / order statistics).
• The operation you're aggregating is invertible (sum, XOR, count) — if it's min/max (non-invertible), lean toward a Segment Tree instead.

Brute force → optimal

Brute force: keep the raw array; on update just overwrite the cell (O(1)); on query, sum a range by walking it (O(n) per query). For q queries and u updates, total cost is O(u + q·n).

Prefix-sum array: query becomes O(1) (P[r]-P[l-1]), but every update now requires re-deriving all prefix sums after that index — O(n) per update.

BIT (optimal): both update and prefix-sum query cost O(log n), because each only visits the O(log n) BIT nodes whose ranges cover the index — derived below.

Mechanism

BIT node i (1-indexed) stores the sum of a range of length lowbit(i) = i & (-i) ending at i: it covers indices (i - lowbit(i) + 1 .. i).

• Query prefix(i): sum tree[i], then jump to i -= lowbit(i), repeat until i == 0. Each jump strips the lowest set bit, so it terminates in at most popcount(i) ≤ log2(n) steps — you're literally decomposing i into its binary representation as a union of disjoint power-of-two-length ranges.
• Update(i, delta): add delta to tree[i], then jump to i += lowbit(i), repeat while i ≤ n. Each jump strictly increases the number of trailing zero bits in i by at least one — adding lowbit(i) to i clears that lowest set bit and carries into a higher position, so it can never repeat or return to a lower trailing-zero count. Since an index up to n has at most ⌊log2 n⌋+1 bits total, the trailing-zero count can take at most that many distinct values, so the chain of ancestors has at most O(log n) steps before i exceeds n.

Complexity, derived

Time: prefixSum strips one set bit per hop, so it runs at most popcount(i) times. update strictly increases i's trailing-zero count by at least one hop, and an index no larger than n has at most ⌊log2 n⌋+1 bits — so trailing-zero count has at most that many possible values, bounding the loop the same way. Either way each loop executes at most ⌊log2 n⌋+1 times → O(log n) per operation. A range query [l,r] is prefixSum(r) - prefixSum(l-1), still O(log n).

Space: exactly one array of size n+1 → O(n), versus a Segment Tree's ~4n array (implementation constant, still O(n) but larger).

Build: naive build (n calls to update) is O(n log n); an O(n) build exists by propagating each tree[i] directly to its parent tree[i+lowbit(i)] once.

Worked example

Array (1-indexed): A = [_, 3, 2, -1, 6, 5, 4, -3, 3] (n=8). Build tree, then query prefixSum(7) and update A[3] += 4.

Java implementation

class Fenwick {
    private final long[] tree;
    private final int n;
    Fenwick(int n) { this.n = n; this.tree = new long[n + 1]; }

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

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

    long rangeSum(int l, int r) { // inclusive, 1-indexed
        return prefixSum(r) - prefixSum(l - 1);
    }
}

Pitfalls

• 0-indexing bug: BIT requires 1-indexed arrays because lowbit(0) is undefined/loops forever; shift external indices by +1.
• Confusing point-update-range-query with range-update-point-query: the latter needs a difference-array trick or a second BIT for range-update+range-query.
• Using BIT for min/max: min/max isn't invertible (no subtraction), so range queries can't be derived from two prefix results — use a Segment Tree instead.
• Forgetting i & (-i) relies on two's-complement; verify language semantics (fine in Java for int/long).

When to use / when NOT — vs Segment Tree

Use BIT when the aggregate is invertible and you want minimal, fast, easy-to-debug code (competitive programming default for range-sum). Use a Segment Tree when you need min/max/gcd, complex range-update+range-query, or custom associative merges.

Takeaways

• BIT exploits the binary representation of indices: lowbit(i) both defines each node's range size and the O(log n) traversal step.
• Query walks down by removing the lowest set bit (bounded by popcount); update walks up by adding it (bounded by trailing-zero count, which strictly grows each hop) — dual, both O(log n).
• Choose BIT over a plain prefix array whenever updates and queries interleave; choose Segment Tree instead when the aggregate isn't invertible.

Recall: Why does update(i, delta) touch at most O(log n) tree cells, and what binary-representation fact guarantees that bound?

Synthesized from standard Fenwick Tree (BIT) references and competitive-programming literature (GeeksforGeeks, CP-Algorithms).