Fenwick Trees (Binary Indexed Trees): Fast Running Totals

The Prefix-Sum Problem and Why Naive Arrays Struggle

A prefix sum (or running total) at position i is the sum of all array elements from the start up to i. Many real problems boil down to answering many prefix-sum or range-sum queries while the underlying data keeps changing. With a plain array there are two obvious strategies, and each one is fast at only one of the two jobs. Strategy one: store the raw array and recompute a sum from scratch whenever someone asks for it, walking through every element in the range. Updates are instant, but a query over a large range takes time proportional to the size of that range, which is unacceptable if you're answering thousands of queries over millions of elements. Strategy two: precompute a running-total array once, so every query is a single subtraction. But now a single update to one element forces you to recompute every prefix sum after it, which again costs time proportional to the array size. Neither approach scales when updates and queries are interleaved and frequent, which is exactly the situation in live analytics, financial tickers, or algorithmic contest problems. The Fenwick tree breaks this tradeoff by storing neither the raw values nor the full running totals, but a cleverly chosen set of partial sums, each responsible for a specific, binary-aligned chunk of the array, so that both operations only ever touch a handful of chunks.

The Lowest-Set-Bit Trick

The heart of a Fenwick tree is a single bitwise operation: isolating the lowest set bit of an index, meaning the rightmost 1-bit in its binary representation. For an index i, this value is computed as i AND (negation of i), often written i & -i in code, and it always equals a power of two. This one number tells the structure exactly how many original array elements a given tree slot is responsible for summing. Slot 6, whose binary form is 110, has lowest set bit 2, so it stores the sum of a 2-element block. Slot 8, binary 1000, has lowest set bit 8, so it stores the sum of a full 8-element block. Slot 5, binary 101, has lowest set bit 1, so it stores just its own single value. This pattern isn't arbitrary: it falls directly out of how binary numbers decompose into powers of two, and it guarantees that any prefix sum can be reconstructed from at most log n of these blocks, and any single update touches at most log n of these blocks. The elegance is that the same simple arithmetic operation, applied repeatedly, drives both directions of the structure: subtracting the lowest set bit walks toward the start of the array for queries, while adding it walks toward the end for updates.

How Updates Propagate

When a value at position i in the original array changes, the Fenwick tree needs to update every partial-sum slot whose block includes position i. It starts at index i itself, applies the change, then repeatedly adds the lowest set bit to move to the next slot that also covers position i, applying the same change there, and continues until the index runs past the end of the array. Because each hop at least doubles the size of the block being touched, this chain of updates has length proportional to log n even for an array of millions of entries. Concretely, updating position 5 in an 8-element tree touches slot 5 (block size 1), then slot 6 (block size 2, since 5 + 1 = 6), then slot 8 (block size 8, since 6 + 2 = 8), and stops because 8 already covers the whole array. Three slots updated instead of potentially thousands. This is the update half of the Fenwick tree's power: rather than eagerly maintaining a full running-total array, it only touches the small set of blocks whose coverage happens to include the changed position, deferring the work of combining values until a query actually asks for them.

How Queries Accumulate

Computing the prefix sum up to position i works as a mirror image of the update process. Starting at index i, the algorithm reads the value stored at that slot, then subtracts the lowest set bit to jump to the slot covering the block immediately before it, adds that value in, and repeats until the index reaches zero. Each subtraction shrinks the index by at least half, so this walk also takes time proportional to log n. For example, the prefix sum up to position 7 in an 8-element tree reads slot 7 (covering just position 7), then jumps to slot 6 (covering positions 5 to 6, since 7 minus 1 equals 6), then jumps to slot 4 (covering positions 1 to 4, since 6 minus 2 equals 4), and stops there since 4 minus 4 equals 0. Adding those three stored values gives the exact sum of positions 1 through 7 without ever touching the seven original elements individually. A range sum from position a to position b, inclusive, is then just the prefix sum up to b minus the prefix sum up to a minus 1, so both point updates and arbitrary range queries reduce to a small handful of array lookups and additions.

A Worked Example and Real-World Uses

Consider an 8-element array with values [3, 2, -1, 6, 5, 4, -3, 3]. Building the Fenwick tree means inserting each value at its own index and letting it propagate upward exactly like an update, so slot 1 ends up holding 3, slot 2 holds 5 (positions 1 to 2), slot 3 holds -1 (its own value), slot 4 holds 10 (positions 1 to 4), slot 5 holds 5, slot 6 holds 9 (positions 5 to 6), slot 7 holds -3, and slot 8 holds 19 (positions 1 to 8, the grand total). Querying the prefix sum up to position 6 then walks slot 6 (9) plus slot 4 (10) for a total of 19 minus the tail, giving 19 correctly reflecting positions 1 through 6. This structure shows up constantly outside the classroom. In competitive programming it's the standard tool for answering many range-sum queries interleaved with point updates in log n time. It's also the workhorse behind counting inversions in an array efficiently, a classic subroutine in sorting-related analysis and in measuring how 'out of order' a sequence is. And in statistics and data engineering, Fenwick trees back frequency tables and order-statistics structures, letting you maintain a running histogram and quickly answer 'how many values seen so far are below x' as new data streams in.

Frequently asked questions

Try it live

Everything above runs in your browser — open Fenwick Trees (Binary Indexed Trees): Fast Running Totals and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.