Point Updates & Prefix Queries

March 2026 · 20 min read

This is where the Fenwick tree comes alive. We implement the two core operations, update(i, delta) and query(i), walk through them step by step with animations, and derive range sum queries from prefix sums.

Prefix Query: sum(1..i)

To compute the prefix sum from index 1 to index i, we accumulate BIT values by stripping the lowest bit at each step:

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

Why does this give the correct prefix sum?

Each BIT[i] stores the sum of lowbit(i) consecutive elements ending at position i. When we strip the lowest bit, we jump to the index immediately before the range that BIT[i] covered. The ranges are perfectly non-overlapping and contiguous, so their sum equals the prefix sum.

For example, query(11):

BIT[11] covers [11, 11]  (lowbit=1)  →  sum += BIT[11]
BIT[10] covers [9,  10]  (lowbit=2)  →  sum += BIT[10]
BIT[8]  covers [1,   8]  (lowbit=8)  →  sum += BIT[8]
                                     →  total = arr[1] + ... + arr[11] ✓

Every prefix can be decomposed this way, the number of terms equals the number of set bits in i, which is at most log₂(n).

Point Update: add delta at position i

To update arr[i] += delta, we walk upward through the BIT by adding the lowest bit at each step:

void update(int i, int delta) {
    while (i <= n) {
        BIT[i] += delta;
        i += i & (-i);  // add lowest bit
    }
}

Why add the lowest bit?

When we add lowbit(i) to i, we jump to the next index whose responsible range contains index i. This is exactly the set of BIT entries that include arr[i] in their partial sum. By updating all of them, every future prefix query that passes through any of these entries will see the change.

For example, update(3, +5) on a size-12 array:

BIT[3]  += 5   (lowbit=1,  covers [3, 3])   → next = 3 + 1 = 4
BIT[4]  += 5   (lowbit=4,  covers [1, 4])   → next = 4 + 4 = 8
BIT[8]  += 5   (lowbit=8,  covers [1, 8])   → next = 8 + 8 = 16 > 12, stop

Range Sum Query: sum(l..r)

A Fenwick tree computes prefix sums, not arbitrary range sums directly. But any range sum can be computed as the difference of two prefix sums:

int range_sum(int l, int r) {
    return query(r) - query(l - 1);
}
// sum(l..r) = prefix(r) - prefix(l-1)

This works because addition is invertible, we can undo a prefix sum by subtracting. This is the fundamental requirement for Fenwick trees: the operation must have an inverse. Sum works (subtract). XOR works (XOR again). But min/max don't, you can't un-min.

The cost is two prefix queries, so range sum is still O(log n).

Complete C++ Implementation

#include <vector>
using namespace std;

class FenwickTree {
    vector<int> bit;
    int n;
public:
    FenwickTree(int n) : n(n), bit(n + 1, 0) {}

    // Build from array in O(n)
    FenwickTree(const vector<int>& arr) : n(arr.size()), bit(arr.size() + 1, 0) {
        for (int i = 1; i <= n; i++)
            bit[i] = arr[i - 1];
        for (int i = 1; i <= n; i++) {
            int p = i + (i & (-i));
            if (p <= n) bit[p] += bit[i];
        }
    }

    // Point update: arr[i] += delta  (1-indexed)
    void update(int i, int delta) {
        for (; i <= n; i += i & (-i))
            bit[i] += delta;
    }

    // Prefix query: sum of arr[1..i]  (1-indexed)
    int query(int i) {
        int s = 0;
        for (; i > 0; i -= i & (-i))
            s += bit[i];
        return s;
    }

    // Range query: sum of arr[l..r]  (1-indexed)
    int query(int l, int r) {
        return query(r) - query(l - 1);
    }
};

That's the entire data structure. ~30 lines, no recursion, no pointers, no extra allocations.

Step-by-Step Walkthrough

Let's trace through a complete example. Starting with arr = [3, 2, -1, 6, 5, 4, -3, 3, 7, 2, 3, 1]:

Complexity Analysis

The constant factor is small: each loop iteration does one addition, one bitwise AND, and one addition/subtraction. No function call overhead, no recursion, excellent cache behavior.

Common Mistakes

1. 0-indexed input: Remember that the BIT is 1-indexed. If your input array is 0-indexed, use update(i + 1, val) and query(i + 1).
2. Forgetting the +1 in range queries: range_sum(l, r) = query(r) - query(l - 1), not query(l).
3. Using update for set (not add): The update function adds a delta. If you want to set arr[i] = val, compute delta = val - arr[i] first, then update(i, delta).
4. Array size: Allocate n + 1 elements, not n. Off-by-one here means writing out of bounds.

Practice Problems

These problems drill the core point-update / prefix-query loop, then push into the classic counting application (inversions via a frequency BIT).