Fenwick Trees (BIT)

The 10-second versionCopy Anchor Link

A Fenwick tree — also called a Binary Indexed Tree (BIT) — keeps cumulative sums available for both fast queries and fast updates, using a single array of the same size as the data. Each slot i secretly owns a small block of elements: exactly the block of length lowbit(i) = i & -i that ends at i. To read a prefix sum you walk down the array, stripping one set bit at a time; to apply an update you walk up, adding the low bit each step. Both walks are O(log n), both use O(n) memory, and the whole thing is about five lines of code.

Why this existedCopy Anchor Link

The story starts with a task that sounds boring but shows up everywhere in signal processing and compression: maintain a cumulative frequency table. You have a stream of symbols, you keep a running count for each one, and you constantly need to ask "how many symbols so far are ≤ x?" — the prefix sum — while also bumping individual counts as new symbols arrive.

There were two obvious ways to hold this, and each was half-broken:

• Keep the raw counts. Updating is O(1), but a prefix query has to add up everything below x — O(n).
• Keep a running prefix table. Querying is O(1), but the moment one count changes, every prefix after it is now wrong — you rebuild in O(n).

Compression algorithms like arithmetic coding hit both operations constantly and fast, so neither "half-broken" option was acceptable.

• 1980s–early 1990s — cumulative frequency tables are a bottleneck in arithmetic coding: each encoded symbol needs both an update and a prefix lookup, millions of times.
• 1994 — Peter Fenwick publishes "A New Data Structure for Cumulative Frequency Tables" in Software: Practice and Experience, giving a structure with O(log n) for both operations and a footprint of one array.
• 1990s–2000s — the structure is rediscovered and popularized under the name Binary Indexed Tree; it becomes a staple of competitive programming for range sums, counting inversions, and order statistics.

Why it mattered then: a compression codec that spends O(n) per symbol is useless — the table maintenance would dwarf the compression. Cutting maintenance to O(log n) with almost no memory made the whole approach practical. And it did it with integers, not pointers — a perfect fit for the machines of the day.

Inside the inventor's headCopy Anchor Link

Fenwick's instinct was to stop treating the array as a flat sequence of positions and start treating the index itself as information. Here's the leap: an index like 12 isn't just "the 12th slot." It's a binary number, 1100, and the position of its lowest set bit says how much work that slot should be responsible for.

Walk the reasoning:

The classic first attempt is to stash a partial sum at every power-of-two boundary. That works, but it's clumsy and full of special cases. The pivot is realizing that every index, not just the powers of two, can own a block — the block size being its lowest set bit. That one generalization makes the query and update walks perfectly symmetric and case-free.

Here's the trap and the fix, side by side. Notice how the naive version has to touch a whole tail of the array on an update:

// Naive: one change invalidates the whole suffix — O(n)function rebuild(a, pre) {  pre[0] = a[0];  for (let i = 1; i < a.length; i++) pre[i] = pre[i - 1] + a[i];}// Fenwick: an update touches only O(log n) slots on its way upfunction update(i, delta, n, tree) {  for (; i <= n; i += i & -i) tree[i] += delta;}

The i & -i expression is the aha written in one line. Negating a two's-complement integer flips every bit and adds one, which leaves exactly the lowest set bit standing: 12 is 1100, -12 is ...0100, and 12 & -12 = 4. That single value tells you how big the block is — and, as we'll see, exactly how far to jump next.

The final approachCopy Anchor Link

What each slot ownsCopy Anchor Link

Slot i stores the sum of the elements in the half-open range (i - lowbit(i), i]. For a 7-element array:

Big low-bit indices own wide blocks; odd indices own a single element. That's why tree[4] can answer "sum of the first four" in one read, while tree[5] holds only a[5].

The two walksCopy Anchor Link

The invariantsCopy Anchor Link

1. Coverage. tree[i] equals the sum of the block (i - lowbit(i), i]. Because lowbit(i) is the largest power of two dividing i, these blocks tile the array exactly.
2. Query decomposition. Any prefix 1..i is the disjoint union of the blocks you meet by repeatedly stripping the lowest set bit of i — that's just reading i in binary, bit by bit from the bottom.
3. Update reach. When you add delta at position i, you must touch exactly the slots whose blocks contain i. Those are found by repeatedly adding lowbit — each step jumps to the next larger nested block that spans the position.

Both walks move at most one set bit per step, so both are bounded by the number of bits — O(log n).

A worked traceCopy Anchor Link

Say the values are [3, 2, -1, 6, 5] at positions 1..5. Build by applying five updates:

Now prefix(5): read tree[5] = 5, drop the low bit → 4; read tree[4] = 10, drop → 0; total 15. Check: 3 + 2 + (-1) + 6 + 5 = 15. ✓ And prefix(2) reads just tree[2] = 5, which is exactly 3 + 2. ✓

A range sum [l, r] is then prefix(r) - prefix(l - 1) — one subtraction, two walks.

It in codeCopy Anchor Link

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

ComplexityCopy Anchor Link

You can build in Θ(n) instead of n updates: for i from 1 to n, let j = i + lowbit(i) and, if j ≤ n, do tree[j] += tree[i]. Each slot is filled once, so it's a single linear pass.

Where you meet it todayCopy Anchor Link

• Counting inversions. "How many pairs are out of order?" reduces to, for each element, asking the BIT for how many smaller values have already been seen — O(n log n) total.
• Order statistics. Store 1 at each present value and the BIT can find the k-th smallest by descending through bit positions — a selection structure in O(log n).
• Compression, the original use. Arithmetic and range coders maintain mutable cumulative frequency tables; a BIT is a natural fit.
• 2D grids. A Fenwick tree of Fenwick trees answers rectangle sums over a matrix, still in O(log² n) — the same trick stacked.

// rank holds each value's compressed rank in 1..nfunction countInversions(rank) {  const n = rank.length;  const bit = new Fenwick(n);  let inv = 0;  for (let i = n - 1; i >= 0; i--) {    inv += bit.prefix(rank[i] - 1);  // smaller values seen to the right    bit.update(rank[i], 1);  }  return inv;}

RecapCopy Anchor Link

• A Fenwick tree answers prefix sums and point updates in O(log n) using one array of size n + 1 — no tree nodes, no recursion, no 4n overhead.
• The magic is the low-bit trick: i & -i gives the length of the block slot i owns, and it also drives both walks.
• Query strips the lowest set bit (i -= i & -i); update adds the low bit (i += i & -i). Both move one set bit per step, hence O(log n).
• Range sums are two prefix queries and a subtraction; building can be done in a single Θ(n) pass.

Next up: Knuth-Morris-Pratt — we leave the array behind and start finding one string inside another, in linear time.