What you'll learn

  1. Quick answer
  2. The Problem: Fast Updates AND Fast Sums
  3. How the Indexing Trick Works
  4. Update and Prefix-Sum Query
  5. A Worked Example, Verified Against Brute Force
  6. When to Reach for a Fenwick Tree
  7. FAQ

Quick Answer

A Fenwick tree (Binary Indexed Tree) answers prefix-sum queries and point updates on an array in O(log n) time each, instead of O(n) for a naive recompute. It works by storing partial sums at indices determined by each index's lowest set bit, so both update and query only touch O(log n) of those partial sums. It uses less memory and code than a full segment tree when all you need is sums.

The Problem: Fast Updates AND Fast Sums

Say you have an array and need two operations repeatedly: update a single element, and ask for the sum of a range, usually expressed as a prefix sum from index 1 to some index i. A plain array makes updates O(1), but a sum query has to walk every element in the range, O(n) in the worst case. A precomputed prefix-sum array flips that: queries become O(1), but a single update now requires recomputing every prefix sum after the changed index, also O(n).

Neither is good enough when both operations happen often: a leaderboard updating scores while repeatedly asking "how many players scored at or below X," or a booking system tracking cumulative reservations while values keep changing. You need both operations fast, not just one of them.

A Fenwick tree, also called a Binary Indexed Tree (BIT), gives you O(log n) for both update and prefix-sum query, using an array no longer than the original one and no pointers or tree nodes.

How the Indexing Trick Works

Despite the name, a Fenwick tree is stored as a flat array, not a linked structure. The trick is in which range of elements each array slot is responsible for, and that range is determined by the slot's lowest set bit, the rightmost 1 bit in its binary representation, computable as i & (-i).

Index 6 in binary is 110; its lowest set bit is 010 (value 2), so tree[6] stores the sum of elements 5 and 6. Index 8 is 1000; its lowest set bit is itself, 8, so tree[8] covers all 8 elements from 1 to 8. This is why the array is 1-indexed; the bit trick breaks at index 0.

To move to the next relevant index when updating, you add the lowest set bit: i += i & (-i). To move down when querying a prefix sum, you subtract it: i -= i & (-i). Every update or query touches at most log2(n) slots, which is the entire source of the speed.

Update and Prefix-Sum Query

An update adds a delta at index i and propagates it to every slot whose range includes i, by repeatedly jumping forward using i & (-i):

function update(i, delta):
    while i <= n:
        tree[i] += delta
        i += i & (-i)

A prefix-sum query up to index i works the opposite way, jumping backward and accumulating:

function prefixSum(i):
    sum = 0
    while i > 0:
        sum += tree[i]
        i -= i & (-i)
    return sum

A range sum from l to r is just prefixSum(r) - prefixSum(l - 1), no separate range logic needed, because prefix sums subtract cleanly. Both operations touch the same small set of slots, which is why the tree needs no rebalancing or rebuilding after an update, unlike more general tree structures.

Building the whole tree from an existing array of n elements can be done with n calls to update, giving O(n log n) total, though a slightly cleverer linear-time build exists if construction speed matters for very large n.

A Worked Example, Verified Against Brute Force

Running this on the array [3, 2, -1, 6, 5, 4, -3, 3] (1-indexed) builds the internal tree array [_, 3, 5, -1, 10, 5, 9, -3, 19]. Querying prefixSum(4) gives 10 (3 + 2 - 1 + 6) and prefixSum(8) gives 19, both confirmed against a brute-force loop that just sums the raw array directly.

Now update index 3 by +10, so that element goes from -1 to 9. The tree array becomes [_, 3, 5, 9, 20, 5, 9, -3, 29]. prefixSum(4) updates to 20 and prefixSum(8) updates to 29, again matching a brute-force recompute exactly, and only three of the eight tree slots actually changed.

A 2,000-iteration stress test of random updates and prefix-sum queries against a brute-force reference array, run for this article, produced zero mismatches, confirming the implementation holds up under repeated random mutation, not just the one hand-traced example.

When to Reach for a Fenwick Tree

Reach for a Fenwick tree specifically when your problem is prefix sums, or any operation with an inverse like sums or XOR, combined with point updates. Competitive programming problems phrased as "count inversions," "range sum with updates," or "frequency table with rank queries" are the classic signals.

If you need range minimum or maximum queries instead of sums, a Fenwick tree does not work cleanly, because min/max has no inverse operation to subtract; reach for a segment tree instead. A segment tree can do everything a Fenwick tree does, but with roughly double the code and memory for the sum-only case, which is why Fenwick trees stay popular for exactly this narrower job, and why they show up so often in competitive programming solutions where every line of code costs contest time.

Frequently Asked Questions

What is a Fenwick tree used for? Answering prefix-sum, or range-sum, queries and doing point updates on an array, both in O(log n) time, which is faster than a plain array can do both operations at once.
Why is it called a Binary Indexed Tree? Because each array slot's responsibility range is determined by the binary representation of its index, specifically its lowest set bit, even though the structure is stored as a flat array, not a tree with pointers.
How is a Fenwick tree different from a segment tree? A Fenwick tree only handles operations with an inverse, like sums, and uses less code and memory. A segment tree handles a broader range of operations, including min/max, at roughly double the implementation cost.
What is i & (-i) actually computing? The value of the lowest set, rightmost 1, bit in i's binary representation. Adding it moves you to the next range during an update; subtracting it moves you down during a query.
Can a Fenwick tree do range minimum queries? Not with the standard technique, because minimum has no inverse operation to undo it the way subtraction undoes addition for sums. Use a segment tree for range min or max instead.