Fenwick tree / segment tree

O(log n) per op

A Fenwick tree stores each slot as the sum of a small block sized by the slot's lowest set bit. update() and query() both jump along a short chain of those blocks, so both run in O(log n) even as data keeps changing.

Signals

range sum or query with point updates interleavedlive leaderboard or running rank while scores changecount inversions or how many earlier values are largerrange queries while the data keeps changing

Template

class Fenwick {
    constructor(n) { this.tree = new Array(n + 1).fill(0); }
    update(i, delta) {
        for (; i < this.tree.length; i += i & -i) this.tree[i] += delta;
    }
    query(i) {
        let sum = 0;
        for (; i > 0; i -= i & -i) sum += this.tree[i];
        return sum;
    }
}

Looks similar, isn't

Prefix sums: Prefix sums answer many range queries fast, but only after the array is built and frozen: one update means rebuilding the whole prefix list. A Fenwick or segment tree keeps both point updates and range queries at O(log n) each, interleaved online, which is what a prefix array cannot do.

n up to 1e5..1e6 with updates and range queries interleaved -> O(log n) per update or query, each walking a short chain of set bits.

Learn this pattern