A Binary Indexed Tree is more than a fast prefix-sum structure. With a small change in what we store - and how we interpret updates - it can handle point updates, range updates, two-dimensional data, and more.
The classic Fenwick Tree pattern.
Change one array position by a given amount, then ask for the sum over any interval. The structure stores partial sums arranged so that a prefix can be assembled from only a logarithmic number of tree entries.
A range is reduced to the difference of two prefixes.
Imagine the current values are:
To query indices 2–4, calculate the prefix through 4 and subtract the prefix through 1. The result is 2 + 7 + 1 = 10.
Store changes, not the full array.
Instead of representing each array value directly, represent how the value changes from one position to the next. Adding a value Δ to every element in an interval only changes two boundaries in this difference representation.
These two boundary changes mean that the extra Δ begins at l and stops after r.
Suppose we add +5 to positions 2 through 4:
The difference structure records +5 at the start and −5 immediately after the end. A prefix sum of these differences tells us the accumulated change at any position.
Two Fenwick Trees — what they store, and why it works.
Let D[i] = A[i] − A[i−1], with A[0] = 0. In other words, D[i] records how much the array changes when we move from position i−1 to position i.
The original value at position i is the sum of all changes up to i:
This is exactly a prefix sum, so a BIT storing D can answer point-value queries.
Now consider adding +3 to positions 2 through 4 of an initially zero array:
Only two differences change: D[2] increases by 3, and D[5] decreases by 3. The second change cancels the addition immediately after the interval.
To find A[i], we sum the differences up to i. But a prefix sum of array values adds those answers together:
Think about one difference D[i]. It contributes to every array value from A[i] onwards. Within the prefix ending at x, it is therefore counted once for A[i], once for A[i+1], and so on through A[x] — a total of x − i + 1 times.
So each difference contributes its value multiplied by the number of times it appears:
Split the multiplier into two parts: x − i + 1 = x − (i − 1). Distributing gives:
That split is the whole trick. We need two prefix sums: the sum of D[i], and the sum of (i−1)·D[i].
At each index i, the underlying value is D[i]. Its prefix query gives the sum of differences through x, which is the current array value A[x].
Its prefix sum supplies the first quantity in the prefix-sum formula.
At each index i, the underlying value is the difference multiplied by one less than its index: (i−1)·D[i].
Its prefix sum supplies the correction term that accounts for how long each difference contributes.
Let sum(B, x) mean “the prefix sum through x in BIT B”. The derivation above now becomes a direct recipe:
To get the sum from l through r, subtract the prefix ending just before l:
Each interval addition updates both BITs at the same two difference boundaries. At a boundary i, if the difference changes by Δ, BIT 1 receives Δ and BIT 2 receives (i−1)·Δ. Each boundary update costs O(log n).
After the update, D[2] = +3 and D[5] = −3; all other differences are zero. Thus BIT 1's underlying values are +3 at index 2 and −3 at index 5. BIT 2's underlying values are (2−1)·3 = +3 at index 2 and (5−1)·(−3) = −12 at index 5.
| Prefix x | sum(B₁, x) | sum(B₂, x) | P[x] = x·sum(B₁,x) − sum(B₂,x) |
|---|---|---|---|
| 3 | 3 | 3 | 3 × 3 − 3 = 6 |
| 4 | 3 | 3 | 4 × 3 − 3 = 9 |
| 5 | 0 | −9 | 5 × 0 − (−9) = 9 |
Check against the actual array [0, 3, 3, 3, 0]: its prefix sums at positions 3, 4, and 5 are 6, 9, and 9. The formula matches each one.
For an addition of Δ on [l, r], the difference array receives +Δ at l and −Δ at r+1. For each of those two changes, update BIT 1 with the difference change itself, and BIT 2 with the change multiplied by (index−1). Both BITs are ordinary Fenwick Trees; only the values supplied to them differ.
The same idea, extended to a grid.
Instead of an array, imagine a matrix with rows and columns. A 2D BIT stores partial sums over rectangular regions aligned with its index structure. Updating one cell and querying a rectangle both take logarithmic time in each dimension.
P(x, y) is the sum of the rectangle from the top-left corner through (x, y).
Green cells illustrate a top-left prefix region.
Assuming standard Fenwick operations and a matrix with R rows and C columns.
| Pattern | Update | Query | Extra space |
|---|---|---|---|
| Point update, range query | O(log n) | O(log n) | O(n) |
| Range update, point query | O(log n) | O(log n) | O(n) |
| Range update, range query | O(log n) per BIT; two BITs total | O(log n) per prefix; two prefixes per range | O(n) |
| 2D BIT: point update, rectangle query | O(log R · log C) | O(log R · log C) per prefix; four prefixes per rectangle | O(RC) |
Big-O suppresses constant factors. A range query may perform multiple prefix queries, but a constant number of logarithmic operations remains logarithmic.
| Need | Choose | Core trick |
|---|---|---|
| Change one element; sum an interval | Pattern 1 | Prefix sums and subtraction |
| Add to an interval; read one element | Pattern 2 | Difference array + one BIT |
| Add to an interval; sum an interval | Pattern 3 | Weighted differences + two BITs |
| Change one grid cell; sum a rectangle | Pattern 4 | 2D prefix sums + inclusion–exclusion |
Fenwick Trees are efficient because they maintain carefully chosen partial aggregates. For interval updates, difference arrays turn a whole range change into two boundary events. For interval sums after interval updates, a second weighted tree supplies the extra information needed to reconstruct prefixes. In two dimensions, the same prefix-and-subtraction principle applies to rectangles.