The ordinary prefix sum is a photograph.

Take an array, sweep left to right, and every position learns how much came before it. That is enough for stream compaction, radix-sort offsets, and many parallel address machines.

But some prefix sums are not photographs. They are ledgers.

In adaptive compression, symbol counts change after each symbol. In an online rank table, inserting one item should change many later ranks. In an order statistic over frequencies, you may need both questions:

what is the cumulative count up to symbol i?
which symbol contains cumulative count k?

A plain array makes an update cheap and a prefix expensive. A prefix-sum array makes a prefix cheap and an update expensive. A segment tree works, but it stores an explicit tree.

A Fenwick tree does a smaller trick. It hides the tree in the binary representation of the index.

The Block Ending Here

Use one-based indexing. Define

\[\operatorname{lowbit}(i) = i \& -i,\]

the largest power of two dividing \(i\). In two’s-complement arithmetic this isolates the least significant set bit.

The Fenwick array \(F\) stores

\[F[i] = \sum_{j=i-\operatorname{lowbit}(i)+1}^{i} A[j].\]

So each cell stores a suffix block ending at itself:

F[12] covers A[9]..A[12]    because lowbit(12) = 4
F[10] covers A[9]..A[10]    because lowbit(10) = 2
F[9]  covers A[9]           because lowbit(9)  = 1

That is the whole object. The index says the block width.

To query a prefix sum at index \(i\), add \(F[i]\), then clear the last set bit:

sum = 0
while i > 0:
  sum += F[i]
  i -= lowbit(i)

For i = 19, the path is

19 -> 18 -> 16

Those blocks cover exactly A[19], A[17]..A[18], and A[1]..A[16].

To update A[i] += delta, walk the other way:

while i <= n:
  F[i] += delta
  i += lowbit(i)

Those are precisely the stored blocks whose ranges contain the edited cell.

Fenwick’s 1994 paper introduced this “binary indexed tree” for maintaining the cumulative frequencies needed in dynamic arithmetic data compression.1 The paper’s summary is refreshingly direct: the structure decomposes cumulative frequencies in a way that parallels the binary representation of the table index, and traversal is based on binary coding of the index. That is why the code is so short. The data structure is mostly arithmetic.

Why Compression Wanted It

Arithmetic coding separates the statistical model from the channel encoding: the model says the next symbol has a probability interval; the coder narrows the current interval accordingly. Witten, Neal, and Cleary’s classic exposition made that separation one of arithmetic coding’s virtues.2

An adaptive model has to update symbol frequencies as it reads the message. For each symbol, it needs cumulative counts:

low(symbol)  = count of all earlier symbols
high(symbol) = low(symbol) + count(symbol)
total        = count of all symbols

If the alphabet is large, recomputing cumulative sums after every symbol is a bad bargain. Fenwick’s structure was designed for exactly this pressure: large-ish dynamic alphabets, frequent updates, and repeated prefix/rank queries. Moffat later proposed improvements to cumulative probability table structures, again in the arithmetic-coding setting.3

The competitive-programming name “BIT” is a little unfortunate because it makes the data structure sound like a trick. It is more like a tiny mutable measure. Every update preserves a cover invariant, and every prefix query decomposes an interval into disjoint low-bit blocks.

The Editable Prefix Lab

The lab below builds a deterministic frequency table, constructs the Fenwick array in linear time, performs one selected update, and then runs three walks:

  1. prefix query;
  2. point update;
  3. rank search, also called finding the first prefix crossing a target count.

The Audit tile is generated by the same JavaScript as the lab. It checks parameter sanitation, low-bit arithmetic, linear build versus repeated updates, the interval invariant for every stored cell, query paths, update paths, prefix differences for range sums, rank search, clipped negative updates, non-power-of- two sizes, and a 1,215-case grid over sizes, seeds, queries, update locations, deltas, and rank targets.

The lab uses one-based indexing internally. Negative updates are clipped so every frequency remains positive; rank search assumes positive frequencies.

At the default setting, the table has 24 frequencies and total count 128. The prefix query at 19 returns 101 by touching only three cells:

19 -> 18 -> 16

The update A[7] += 5 touches:

7 -> 8 -> 16

After the update, the same prefix sum becomes 106. The updated total is 133; a 62% rank target is count 83, and the rank search finds index 16 after five bit decisions.

The Third Operation: Search by Mass

Prefix query and point update are the usual Fenwick tree operations. The rank operation is the one that makes the compression origin feel alive.

Given a target count \(k\), find the smallest index \(i\) such that

\[\sum_{j=1}^{i} A[j] \ge k.\]

This is a discrete inverse CDF. In arithmetic decoding, the coded value lands inside a cumulative-frequency interval; the model has to find which symbol owns that interval.

A naive way would binary-search over prefix sums, costing \(O(\log^2 n)\) if each prefix query costs \(O(\log n)\). Fenwick trees can do it in \(O(\log n)\) by descending powers of two. Start at the highest power of two not exceeding \(n\). Tentatively jump right. If the cumulative block there is still below the target, keep the jump and subtract the block. Then halve the jump size.

The code looks like it is walking bits because it is walking bits:

idx = 0
bit = highest_power_of_two_at_most(n)
while bit > 0:
  next = idx + bit
  if next <= n and F[next] < target:
    idx = next
    target -= F[next]
  bit /= 2
return idx + 1

This search only works as an order search when frequencies are nonnegative, and the lab keeps them positive. With arbitrary signed updates, prefix sums are no longer monotone and “first crossing” stops being a well-defined inverse CDF.

That is a useful boundary. Fenwick trees are not magic arrays. They are compact machines for an algebra and a query pattern. Change the algebra or the query, and the machine may no longer be the right one.

What the Low Bit Is Buying

The low bit buys a canonical tiling of prefixes.

Every positive integer has a binary expansion. Clearing the lowest set bit removes one power-of-two block from the end. Repeating this decomposes the prefix 1..i into disjoint blocks whose endpoints are exactly the Fenwick cells you visit.

For example,

19 = 16 + 2 + 1

and the query path uses block widths:

1, 2, 16

ending at:

19, 18, 16

The update walk is the dual. It visits every block that will need to know about the changed cell. Adding lowbit(i) moves to the next larger block whose suffix range still covers the edited index.

That is why the structure is compact. It does not store all prefix sums. It stores just enough overlapping suffix blocks that any prefix can be tiled by clearing bits, and any point update can be propagated by adding bits.

The tree is there. You just never allocated nodes for it.

  1. Peter M. Fenwick, “A New Data Structure for Cumulative Frequency Tables”, Software: Practice and Experience 24(3), 1994. Wiley record: https://onlinelibrary.wiley.com/doi/10.1002/spe.4380240306. ↩

  2. Ian H. Witten, Radford M. Neal, and John G. Cleary, “Arithmetic Coding for Data Compression”, Communications of the ACM 30(6), 1987. ↩

  3. Alistair Moffat, “An Improved Data Structure for Cumulative Probability Tables”, Software: Practice and Experience 29(7), 1999. ↩