Implementation of Binary Indexed Tree

A Binary Indexed Tree (Fenwick Tree) answers prefix-sum queries and point updates in O(log n) by storing, at each index i, the sum of a range whose length equals the lowest set bit of i — so both reading a prefix and updating a value only ever touch O(log n) of these overlapping ranges instead of the whole array.

Recognize the pattern

• You need prefix sums / range sums that change online — repeated point updates interleaved with sum queries (naive re-summing would be O(n) per query).
• Data is 1-indexed integers over a fixed range, and you only need sum, count, or XOR-type aggregates — not arbitrary min/max over arbitrary ranges (that needs a segment tree instead).
• Keywords in the problem: "number of elements ≤ x seen so far", "running sum with updates", "inversion count", "range update + point query".

Brute force → optimal

BIT is the sweet spot when both operations must be fast and interleaved — neither the plain array nor the precomputed prefix array handles mixed update/query workloads well.

Mechanism: two opposite walks

bit[i] stores the sum of the input range (i - lowbit(i), i] (1-indexed), where lowbit(i) = i & -i is the value of the lowest set bit. The two operations walk the index in opposite directions using that same value:

Update moves up the tree: i += lowbit(i) (widen to the next range that also covers this element) until i > n. Query moves down/left: i -= lowbit(i) (walk to the previous disjoint block) until i == 0. Note the two right-hand columns are never equal for the same row — one adds lowbit, the other subtracts it, which is the whole trick.

Complexity, derived

Update: each step sets a bit that was 0 in i's binary form, moving to a strictly larger index; since i ≤ n has at most log₂(n)+1 bits, at most that many steps run before i > n ⇒ O(log n). Query: each step clears the lowest set bit of i; the number of set bits in i is at most log₂(i) ⇒ at most O(log n) steps to reach 0. Space: one array of size n+1 ⇒ O(n), no extra pointers or child lists needed.

Worked example

Array (1-indexed, n=11): [3, 2, -1, 6, 5, 4, -3, 3, 7, 2, 3].

Query trace — prefix sum through index 6 (elements 1..6): 3+2-1+6+5+4 = 19. Walk with i -= lowbit(i):

Update trace — update(5, +3) (element 5 changes from 5 to 8, delta = +3). Walk with i += lowbit(i), adding the delta to every bit[i] visited:

Exactly three slots — bit[5], bit[6], bit[8] — needed the +3, because those are precisely the ranges that include index 5. Every other bit[i] is untouched. Note this walk moves the opposite direction from the query trace above (5→6→8, increasing) even though both use the same lowbit value at each step.

class BIT {
    private final long[] tree;
    private final int n;

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

    // add delta at 1-indexed position i
    void update(int i, long delta) {
        for (; i <= n; i += i & (-i)) {
            tree[i] += delta;
        }
    }

    // sum of a[1..i], 1-indexed, inclusive
    long prefixSum(int i) {
        long sum = 0;
        for (; i > 0; i -= i & (-i)) {
            sum += tree[i];
        }
        return sum;
    }

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

    // O(n) build: apply raw values then push each into its parent
    static BIT build(long[] values1Indexed) {
        int n = values1Indexed.length - 1;
        BIT bit = new BIT(n);
        System.arraycopy(values1Indexed, 0, bit.tree, 0, n + 1);
        for (int i = 1; i <= n; i++) {
            int parent = i + (i & (-i));
            if (parent <= n) bit.tree[parent] += bit.tree[i];
        }
        return bit;
    }
}

The naive build calls update n times for O(n log n); the build method above pushes each node's value into its parent once, giving true O(n) construction.

Pitfalls

• Off-by-one / 0-indexing — BIT is inherently 1-indexed because lowbit(0) = 0 & -0 = 0; if an update loop started at i = 0, the step i += lowbit(i) would add 0 forever, so i never advances and the loop never terminates (a stuck traversal, not undefined behavior — the arithmetic is perfectly well-defined, it just never changes i). Convert external 0-indexed arrays by adding 1 everywhere.
• Forgetting range-sum needs a subtraction — rangeSum(l, r) = prefixSum(r) - prefixSum(l-1), not prefixSum(r) - prefixSum(l).
• Using it for range-min/max — the subtraction trick only works for invertible operations (sum, XOR); min/max is not invertible, so BIT can't do range-min queries without extra tricks.
• Confusing update with set — update(i, delta) adds a delta; to set a value, first compute delta = newVal - oldVal.

When to use / when not

Use when you need point-update + prefix/range-sum (or count, or XOR) queries interleaved, want a compact array-based structure, and don't need range assignment or non-invertible aggregates.

Prefer a Segment Tree instead when you need range-min/max/gcd, range updates with lazy propagation, or more complex merge operations — segment trees generalize to any associative operation at the cost of ~2x the memory and a slightly larger constant factor, but the same O(log n) time bounds.

Takeaways

• BIT trades a tree's flexibility for a flat array and two bit tricks that move in opposite directions: i += i&-i widens the range for update, i -= i&-i narrows it for query.
• Both operations are bounded by the number of bits in n → O(log n) time, O(n) space.
• It only works for invertible aggregates (sum, XOR); reach for a segment tree for min/max or range updates.
• It nests to higher dimensions: a 2D BIT runs the i += i&-i loop on both coordinates, giving O(log²n) point-update and rectangle-sum on a matrix — the same bit trick, one loop per axis.

Recall: Why does i & -i isolate the lowest set bit — and why does adding it walk update up toward larger indices while subtracting it walks query down toward zero, using the very same value?

Synthesized from standard competitive-programming references on Fenwick/Binary Indexed Trees (Peter M. Fenwick, 1994) and common interview-prep treatments of prefix-sum data structures.