Fenwick trees (BIT): the 12-line workhorse

Sparse tables are static. The moment updates interleave with queries — "add 3 to a[7], now what is sum(2, 9)?" — you need a structure that does both in O(log n). The Fenwick tree, or Binary Indexed Tree, is the smallest one that exists: a dozen lines, resting entirely on one bit trick.

The trick is lowbit: i & (−i) isolates the lowest set bit of i. In two's complement, −i flips every bit and adds one, which leaves only the lowest set bit surviving the AND. Index i in the tree is responsible for a block of lowbit(i) elements ending at i.

long long bit[N+1];  // zero-initialized

void update(int i, long long v) {      // a[i] += v
    for (; i <= N; i += i & -i)
        bit[i] += v;
}

long long query(int i) {               // prefix sum a[1..i]
    long long s = 0;
    for (; i > 0; i -= i & -i)
        s += bit[i];
    return s;
}

Trace query(13). Start at 13 = 1101₂, add bit[13]; subtract lowbit (1) → 12 = 1100₂, add bit[12] (which covers a[9..12], since lowbit(12) = 4); subtract lowbit (4) → 8 = 1000₂, add bit[8] (covers a[1..8]); subtract lowbit (8) → 0, stop. Three nodes summed give the whole prefix to 13 — each step strips one set bit, so the loop runs once per set bit: O(log n).

long long query(int i) {
    long long s = 0;
    for (; i > 0; i -= i & -i)
        s += bit[i];
    return s;
}

// query(11): which i values?

A range sum is then just query(r) − query(l − 1), back to the prefix-subtraction idea but now with O(log n) updates underneath it. The whole structure is a few lines because the binary structure of the indices is the tree — there are no child pointers, no nodes, just an array and the lowbit walk.

Fenwick is the reach-for-it default whenever the aggregate is a sum (or anything invertible). Its one limitation is exactly that invertibility: it cannot do range min with updates, because you cannot subtract a minimum back out. For that — and for anything more exotic — you need the general hammer.