The problem changes when values can change
Let be an array of integers, where . We want to interleave two operations: add an integer to one entry , and ask for the sum of a contiguous interval . Recomputing an interval directly costs up to additions. A prefix-sum array makes interval queries fast, since
But changing changes every prefix . An ordinary prefix-sum array therefore trades constant-time queries for potentially linear-time updates. A binary indexed tree, also called a Fenwick tree, stores selected interval sums instead. Its selection is designed so that both a query and an update visit only logarithmically many stored intervals. The word “tree” describes relationships between array indices; an implementation does not need pointer-based nodes.
We use one-based indexing throughout. Integer arithmetic in the explanation is exact. A program must choose a sum type large enough for the accumulated values; a small individual entry does not guarantee a small interval sum.
What one tree entry means
Definition 1.1.1
(The least significant set bit and its interval)
For a positive integer , let be the largest power of two dividing . If with odd, then . The tree invariant is
Write for this inclusive index interval.
For example, has lowbit , so stores indices
. The lowbit is a length, not the first index of the interval.
In the usual fixed-width binary representation, i & (-i) computes it
for a positive index, using two's-complement negation: negation preserves
the lowest set bit, leaves the lower zero bits unchanged, and complements
the bits above it, so the bitwise AND retains only that one bit. The mathematical definition above
is independent of a programming language's representation rules.
Worked example 1.1.2
(All stored intervals for an eight-entry array)
Start from
| Stored interval | |||
|---|---|---|---|
These intervals overlap. A query must select a disjoint subcollection; adding every stored entry would count some original values several times.
Prefix queries remove one completed block at a time
To obtain , take the block ending at . Its left neighbor is the prefix ending at . Repeat on that remaining prefix.
PREFIX(r): // precondition: 0 <= r <= n
total = 0
i = r
while i > 0:
total = total + T[i]
i = i - lowbit(i)
return total
RANGE_SUM(l, r): // precondition: 1 <= l <= r <= n
return PREFIX(r) - PREFIX(l - 1)
Proposition 1.1.3
(Prefix query by completed blocks)
For , PREFIX(r) returns . It adds the entries for the indices obtained from by repeatedly subtracting the lowbit, and the corresponding blocks are pairwise disjoint with union .
Proof
(Why a prefix query neither skips nor repeats an entry)
Let denote the original query endpoint. At the start of each iteration, maintain
Initially the total is zero and . The stored block is exactly the last entries of the remaining prefix. Adding that block to the total and replacing by therefore preserves the equation. Since the lowbit is positive, the nonnegative index strictly decreases until it reaches zero. The remaining sum is then empty, so the returned total is exactly . Every chosen block lies immediately to the right of the next remaining prefix, proving disjointness as well as coverage.
In the example, PREFIX(7) visits and returns
. The blocks are , , and .
Their order is right to left, but their union is precisely .
The call PREFIX(0) returns zero immediately; it never reads .
Concept lensAlgebraic
A prefix is read off the binary expansion of its length
Write with . Subtracting lowbits removes these powers in this order, so the blocks of PREFIX(r) have lengths , read from the right end of . For the lengths are , the blocks , , . The query is the statement that the integer splits into its binary digits, applied to an interval.
A point addition changes every stored block containing that point
If increases by , a stored interval changes by exactly when it contains . All other stored intervals must remain unchanged. The update path enumerates precisely those containing intervals:
ADD(p, delta): // precondition: 1 <= p <= n
i = p
while i <= n:
T[i] = T[i] + delta
i = i + lowbit(i)
Indices in this pseudocode are mathematical integers. The addition computing the next index must be representable in an implementation, including the last step that moves beyond .
Proposition 1.1.4
(The update path touches exactly the containing blocks)
For and an integer , the loop ADD(p, delta) adds to exactly once for each with , and changes no other entry. Afterwards the tree invariant holds for the array in which is replaced by .
Proof
(Why the update path finds all and only the affected blocks)
The first visited block contains . Suppose a visited index has lowbit , and put . Since is odd, is divisible by . Consequently
so contains the entire block . In particular it contains . Thus every visited block really must receive the update.
We must also show that no affected block is skipped. Any possible block containing has endpoint at least . Between successive visited indices and , consider with . The lower bits of are zero, so . Therefore
The first index of is strictly greater than , so cannot contain . There are no candidates before the first endpoint , and the same argument excludes every gap between path endpoints, including the final gap when the next endpoint exceeds . The loop therefore updates each affected block exactly once. Its invariant is restored after the point addition, ready for every later query.
Proof X-ray
A query path and an update path answer different questions
The key step of the update proof is the divisibility for when is odd. Adding the lowbit carries into a higher bit, so the next block is strictly longer and contains the previous one. That nesting is why the visited blocks form exactly the chain of blocks containing . The query proof uses the opposite structure: subtracting the lowbit leaves a prefix that ends exactly where the removed block begins, so the blocks are disjoint rather than nested.
Nesting alone shows only that every visited block is affected. That nothing is missed needs the separate gap argument: for with the lowbit of equals that of , so starts after . The bound only stops the loop and plays no part in either argument. The opposite signs of the two loops are consequences of these two different invariants, not formulas to memorize.
Worked example 1.1.5
(Update an entry and check an interval query)
Starting from the eight-entry example, apply ADD(5, 2). The update visits
and then reaches , outside the tree. The changed entries are
Every other stays as before. Now PREFIX(7) returns
. Hence
Directly, the changed interval contains , whose sum is . An update to position must not modify , because misses that position. The query path and the update path share some indices, but neither path can be substituted for the other.
Worked example 1.1.6
(A size that is not a power of two)
Take and for every , so : for instance , , . Now apply ADD(9, 3). The path is : lowbit moves to , lowbit moves to , lowbit moves to , which exceeds and stops the loop. So , , . The entries and miss position and stay unchanged. Then PREFIX(13) visits and returns , as it should.
Common mistake
(Reading the lowbit as the first index of the block)
For the lowbit is . Taking as the start of the block gives , nine entries, which is wrong. The lowbit is the length of the block: and .
Common mistake
(Adding the new value instead of the change)
To set on the eight-entry array, the call ADD(5, 2) makes and , since was . The required change is , which gives . ADD always adds; it never sets.
Trace the invariant on signed data
The worked example above uses a positive array. The figure below uses two different fixed arrays, including negative values; it is a new example, not a continuation of the preceding update. Each selected operation restarts from the chosen array. A displayed target array describes the requested result of an addition, even while some tree entries are still awaiting their update.
The stored intervals depend on the indices, not on the signs of their values. A nonempty block can sum to zero and must still be read when its interval belongs to the query. Similarly, adding zero still visits the affected entries although none of their numbers changes. Keep visit progress separate from numerical equality with the target.
Start with the prefix query, then compare a point addition: subtraction of lowbit removes a completed query block, while addition of lowbit finds the next containing block. The two paths certify different claims. The empty query prefix(0) is valid; an update at position zero is not.
Why both operations are logarithmic
Proposition 1.1.7
(Logarithmic cost of both operations)
Let . For , PREFIX(r) performs at most iterations. For , ADD(p, delta) visits at most indices. The tree stores sums.
Proof
(Clearing bits and doubling lowbits)
In a query, subtracting the lowbit clears the lowest set bit of the index. Thus the number of iterations equals the number of set bits of the original , at most when . In an update, the next index has lowbit at least twice the current lowbit, as proved above. Each in-bounds index has lowbit at most , so again there are at most visits. The update index need not double: moves to , not . It is the lowbit that at least doubles. ∎
The tree uses stored sums, so its memory cost is . Starting with
a zero tree and applying ADD(i, a_i) for each constructs the invariant
in time. This is a correct simple construction; it is not a
claim that linear-time construction is impossible. The proofs do not assume
that is a power of two: for , PREFIX(13) visits , and
an update at still visits before leaving the index range.
Addition, assignment, and the algebra behind interval subtraction
ADD(p, delta) adds a change; it does not set to that argument.
To assign a new value , compute , apply the addition, and
record if a separate copy of the array is maintained. Without that
copy, the old value can be recovered by RANGE_SUM(p, p) in logarithmic time.
For example, on the original array, assigning requires ,
not an addition of . The resulting are .
Negative values and negative changes are valid for the sum invariant.
Counterexample mode
Replacing sums by minima does not preserve these formulas
The arrays and have the same prefix minima at endpoints and : both are . Yet their minima on are and . Thus those two prefix minima cannot determine an arbitrary interval minimum. There is no analogue of subtracting a prefix sum to undo an earlier minimum.
Updates also change character. If a stored interval contains values , its minimum is . Increasing the first value to makes the new minimum ; taking the minimum of the old stored value and new value would incorrectly leave . Restricted minimum-query variants need their own invariants and update assumptions. The unrestricted additive proof here does not justify them.
Practice with complete solutions
In each question, reset to the original eight-entry array.
Quick check
(Which entries contribute to PREFIX(6)? Give their stored intervals.)
Solution · Answer
The path is , selecting and . Its answer is .
Quick check
(Apply ADD(3, -4). Which tree entries change, and what is the new RANGE_SUM(3, 7)?)
Solution · Answer
The update path is , giving .
Originally the sum on was , so the new answer is .
The query calculation agrees: PREFIX(7) is , and
PREFIX(2) is , giving .
Quick check
(Why would calling the update loop with fail to make progress?)
Solution · Answer
The positive-index definition of lowbit does not apply at zero. Even if code evaluates the bit expression there and gets zero, the next index remains zero, producing an endless loop. Convert a zero-based external position to the internal position before an update.
Quick check
(Assign . Find PREFIX(7) and explain why the update argument is negative.)
Solution · Answer
The change is , so PREFIX(7) becomes .
Adding instead would change the entry to , solving a different task.
For implementation comparisons and additional variants, see the CP-Algorithms Fenwick-tree article.