Fenwick Tree

Overview

A Fenwick tree, also called a Binary Indexed Tree (BIT), maintains partial sums so that you can efficiently update individual values and calculate totals over ranges.

Its main advantage is balance: both point updates and range-sum queries take O(log n) time. A plain array makes updates cheap but range queries expensive; a prefix-sum array makes queries cheap but updates expensive. A Fenwick tree avoids either operation becoming a full-array traversal. The AtCoder Library Fenwick tree documents both operations in O(log n) time.

The implementation is surprisingly small. Most of the apparent mystery comes from two lines:

i -= i & -i  # Used while querying.
i += i & -i  # Used while updating.

These are not arbitrary bit tricks. They navigate carefully chosen blocks of the array.

Once you understand what each block stores, the implementation becomes much easier to reason about.

The Problem: Fast Queries and Fast Updates

Suppose an application maintains counts for eight consecutive time periods:

values = [3, 2, 5, 1, 4, 6, 2, 7]

It needs to support two operations:

# Increase the value at index 2 by 4.
values[2] += 4

# Calculate the total from index 2 through index 5.
sum(values[2:6])

With a plain array, the update changes one element. However, calculating a range sum requires visiting every element in that range.

A prefix-sum array reverses the trade-off:

prefix = [0]

for value in values:
    prefix.append(prefix[-1] + value)

# Sum of values[left:right].
total = prefix[right] - prefix[left]

Queries now need only two lookups and a subtraction. But changing an input value can invalidate every prefix sum after it.

Plain Array vs. Prefix Sums vs. Fenwick Tree

The following comparison assumes a fixed-length array and constant-time arithmetic. Fenwick trees and segment trees both support logarithmic updates and range queries, but a segment tree supports a broader range of aggregation operations.

The important question is not “Which data structure is fastest?” It is which operations happen frequently enough to justify maintaining additional structure. For immutable data, a Fenwick tree can be unnecessary complexity. For interleaved updates and range queries, it becomes much more attractive.

What a Fenwick Tree Actually Stores

A Fenwick tree does not store a complete prefix sum at every index. It stores selected partial sums.

We will use:

• Zero-based indices for the public array.
• One-based indices inside the Fenwick tree.
• Half-open ranges such as [left, right), meaning the left endpoint is included and the right endpoint is excluded.

For example, [2, 6) contains indices 2, 3, 4, and 5.

Define:

lowbit = i & -i

The internal entry bit[i] stores:

sum(values[i - lowbit:i])

In other words, it stores the sum of lowbit elements ending just before public index i.

A Visual Example

For:

values = [3, 2, 5, 1, 4, 6, 2, 7]

Each X below marks an input element included in a stored block:

Array index:   0  1  2  3  4  5  6  7
Array value:   3  2  5  1  4  6  2  7

bit[1]:        X  .  .  .  .  .  .  .    sum =  3
bit[2]:        X  X  .  .  .  .  .  .    sum =  5
bit[3]:        .  .  X  .  .  .  .  .    sum =  5
bit[4]:        X  X  X  X  .  .  .  .    sum = 11
bit[5]:        .  .  .  .  X  .  .  .    sum =  4
bit[6]:        .  .  .  .  X  X  .  .    sum = 10
bit[7]:        .  .  .  .  .  .  X  .    sum =  2
bit[8]:        X  X  X  X  X  X  X  X    sum = 30

Therefore:

bit = [0, 3, 5, 5, 11, 4, 10, 2, 30]

Index 0 is unused.

Notice that bit[6] is not the sum of the first six values. It stores only:

values[4] + values[5]  # 4 + 6 = 10

To obtain a complete prefix sum, the query combines several non-overlapping blocks.

The structure is called a tree because these blocks have implicit relationships. There are no explicit node objects or child pointers in this implementation.

Understanding i & -i

The expression:

i & -i

isolates the lowest set bit of a positive integer. The result is a power of two—not the position of that bit.

For example:

i = 12

Binary:       1100
Lowest set:   0100

i & -i = 4

The lowest set bit is also the largest power of two that divides i:

12 is divisible by 4, but not by 8.
Therefore lowbit(12) = 4.

Why Does Negation Isolate That Bit?

Using an eight-bit illustration of two’s-complement arithmetic:

 i       = 00001100    12
~i       = 11110011
-i       = 11110100    invert the bits, then add 1

i & -i   = 00000100     4

Suppose a positive integer i ends in a 1 followed by k zeros. Inverting the bits changes that suffix to a 0 followed by k ones. Adding one changes it back to a 1 followed by k zeros, while the higher bits remain inverted. The AND therefore preserves only the original lowest set bit, whose value is 2**k.

Python’s bitwise operations behave as though integers use two’s complement with an unlimited number of sign bits (Python documentation: bitwise operations on integer types), so this identity also works for Python’s arbitrary-precision integers (Python documentation: numeric types).

For a Fenwick tree, the result tells us the length of the block stored at bit[i].

i       Binary       lowbit(i)       Block length
1       0001         1               1
2       0010         2               2
3       0011         1               1
4       0100         4               4
6       0110         2               2
8       1000         8               8

Prefix Queries: Consume Blocks Without Changing Them

Suppose we want:

sum(values[:7])

That is the sum of the first seven elements.

The query starts at internal index 7:

i = 7
Read bit[7]: values[6:7] = 2
Move to 7 - 1 = 6

i = 6
Read bit[6]: values[4:6] = 10
Move to 6 - 2 = 4

i = 4
Read bit[4]: values[0:4] = 11
Move to 4 - 4 = 0

Stop.

The result is:

2 + 10 + 11 = 23

The query partitions the prefix into adjacent, non-overlapping blocks:

[0, 7) = [0, 4) + [4, 6) + [6, 7)

This explains the subtraction:

i -= i & -i

After consuming the block ending at i, subtract its length to reach the end of the remaining prefix.

Does Querying Mutate the Tree?

No. A standard Fenwick sum query only reads the tree.

total += bit[i]  # Read a stored sum.
i -= i & -i     # Change the local traversal index.

Only local variables change. The stored bit entries remain untouched. The official AtCoder implementation uses this same separation: its update writes to the backing array, while its prefix query only reads it.

For a longer array, querying the first thirteen elements follows:

13 -> 12 -> 8 -> 0

Those indices correspond to:

[12, 13) + [8, 12) + [0, 8)

The block lengths are 1, 4, and 8, which add up to thirteen.

The bit manipulation is simply an efficient way to decompose the prefix.

Point Updates: Change Every Block That Contains an Element

Now suppose we apply:

values[2] += 4

Public index 2 becomes internal index 3.

Looking at the diagram, that value contributes to:

bit[3]   covers [2, 3)
bit[4]   covers [0, 4)
bit[8]   covers [0, 8)

Each of those stored sums must increase by four:

bit[3]:   5 ->  9
bit[4]:  11 -> 15
bit[8]:  30 -> 34

The update traversal is:

3 -> 4 -> 8 -> stop

It uses:

i += i & -i

This moves to the next containing block in the update chain. Blocks that do not contain the changed element are skipped.

Query vs. Update

The two loops use the same bit operation, but they do different jobs: queries assemble an answer; updates maintain the stored answers.

A Complete Python Implementation

This implementation provides a zero-based public interface and uses half-open query ranges.

It also builds the tree in O(n) time rather than inserting every initial value through an O(log n) update.

from collections.abc import Iterable


class FenwickTree:
    """Point updates and half-open range sums over a fixed-length array."""

    def __init__(self, values: Iterable[int]):
        self.bit = [0, *values]
        self.n = len(self.bit) - 1

        # Forward each completed block to its containing parent.
        for i in range(1, self.n + 1):
            parent = i + (i & -i)
            if parent <= self.n:
                self.bit[parent] += self.bit[i]

    def add(self, index: int, delta: int) -> None:
        """Apply values[index] += delta."""
        if not 0 <= index < self.n:
            raise IndexError("index out of range")

        i = index + 1
        while i <= self.n:
            self.bit[i] += delta
            i += i & -i

    def prefix_sum(self, end: int) -> int:
        """Return sum(values[0:end]); end is exclusive."""
        if not 0 <= end <= self.n:
            raise IndexError("prefix endpoint out of range")

        total = 0
        i = end
        while i > 0:
            total += self.bit[i]
            i -= i & -i
        return total

    def range_sum(self, left: int, right: int) -> int:
        """Return sum(values[left:right])."""
        if not 0 <= left <= right <= self.n:
            raise IndexError("invalid range")

        return self.prefix_sum(right) - self.prefix_sum(left)

    def set(self, index: int, value: int) -> None:
        """Assign values[index] = value."""
        current = self.range_sum(index, index + 1)
        self.add(index, value - current)

Example Usage

values = [3, 2, 5, 1, 4, 6, 2, 7]
tree = FenwickTree(values)

print(tree.prefix_sum(7))    # 23
print(tree.range_sum(2, 6))  # 16

tree.add(2, 4)               # Index 2 changes from 5 to 9.
print(tree.range_sum(2, 6))  # 20

tree.set(4, 10)              # Index 4 changes from 4 to 10.
print(tree.range_sum(2, 6))  # 26

print(tree.prefix_sum(0))    # 0
print(tree.range_sum(3, 3))  # 0

The constructor copies the input values. Updating the tree does not update the original values list.

Adding Is Not Assigning

These calls have different meanings:

tree.add(2, 10)  # Increase index 2 by 10.
tree.set(2, 10)  # Make index 2 equal to 10.

The usual Fenwick update accepts a delta, not a replacement value. Assignment must calculate:

delta = new_value - current_value

Our implementation retrieves the current value through a range query. Alternatively, it could retain a separate array of current values. That saves query work during assignment but consumes additional storage.

Why the Linear Build Works

Initially, each internal entry contains one input value.

Processing indices in increasing order ensures that a block has received contributions from its smaller descendants before forwarding its total to its parent.

Each index performs at most one such forwarding operation:

self.bit[parent] += self.bit[i]

There are n indices, so construction takes O(n) time.

Building an empty tree and calling add() for every input is also correct, but costs O(n log n).

Why Queries and Updates Are O(log n)

A prefix query clears one set bit from its index on each iteration.

For example:

13 = 1101
12 = 1100
 8 = 1000
 0 = 0000

The number of iterations equals the number of set bits in the starting prefix endpoint. An index bounded by n has only O(log n) binary digits.

Updates also take logarithmically many steps. Each addition carries into a higher bit position, making the next block larger.

A range query performs two prefix queries:

range_sum(left, right) = prefix_sum(right) - prefix_sum(left)

Therefore it is still O(log n), not O(log² n).

For an array of one million elements, a prefix query needs at most about twenty stored-block reads. A full-range sum using a direct scan could inspect one million elements.

That is an operation-count comparison, not a wall-clock speedup claim. Interpreter overhead, memory access, query lengths, and workload distribution still affect actual performance.

The construction, point updates, prefix sums, and range sums above are the core of this structure. The following sections extend it to frequency problems and range updates.

Practical Example: Counting Inversions

An inversion is a pair of positions where an earlier value is greater than a later value:

i < j, but values[i] > values[j]

For:

[3, 1, 2]

The inversions are (3, 1) and (3, 2).

A Fenwick tree can solve this by maintaining a frequency table.

Scanning from right to left:

1. Count how many already-seen values are smaller than the current value.
2. Add that count to the answer.
3. Record one occurrence of the current value.

Coordinate Compression

Values might be negative, sparse, or extremely large. Allocating a slot for every possible value would be wasteful.

Instead, assign sorted distinct values consecutive ranks:

Original values:  -50, 100, 1,000,000
Compressed rank:   0,   1,         2

This preserves ordering, which is all inversion counting needs.

from collections.abc import Sequence


def count_inversions(values: Sequence[int]) -> int:
    ranks = {
        value: i
        for i, value in enumerate(sorted(set(values)))
    }

    tree = FenwickTree([0] * len(ranks))
    inversions = 0

    for value in reversed(values):
        rank = ranks[value]

        # Ranks [0, rank) are strictly smaller.
        inversions += tree.prefix_sum(rank)
        tree.add(rank, 1)

    return inversions

print(count_inversions([3, 1, 2]))  # 2
print(count_inversions([2, 2, 1]))  # 2

Equal values receive the same rank and are deliberately excluded from the query. They do not count as inversions.

Sorting the distinct values and processing the array give an overall O(n log n) bound.

Nuance: compression preserves order, not distance. The gap between ranks 1 and 2 does not represent the numeric gap between their original values. It also assumes the relevant value universe is known; inserting previously unseen values between existing ranks can require rebuilding the mapping.

Finding the kth Item in a Frequency Table

Fenwick trees can also search cumulative frequencies. Instead of asking “What is the total before this position?”, ask:

“At which position does the running total first reach k?”

This supports rank selection and changing weighted distributions. A direct traversal through Fenwick blocks avoids binary-searching positions with a separate prefix query at each step. KACTL’s Fenwick implementation includes this cumulative-search operation.

Consider:

frequencies = [2, 0, 3, 1]

Conceptually, the items are:

Position:       0  0  2  2  2  3
Item number:    1  2  3  4  5  6

The third item belongs to position 2.

def find_by_order(tree: FenwickTree, k: int) -> int:
    """
    Return the zero-based position containing the kth item.

    k is one-based.
    Requires nonnegative integer frequencies.
    """
    if not 1 <= k <= tree.prefix_sum(tree.n):
        raise ValueError("k must be between 1 and the total frequency")

    index = 0
    step = 1 << (tree.n.bit_length() - 1)

    while step:
        candidate = index + step

        if candidate <= tree.n and tree.bit[candidate] < k:
            index = candidate
            k -= tree.bit[candidate]

        step >>= 1

    return index

tree = FenwickTree([2, 0, 3, 1])

print(find_by_order(tree, 1))  # 0
print(find_by_order(tree, 3))  # 2
print(find_by_order(tree, 6))  # 3

index tracks the length of the prefix already skipped. The search tries progressively smaller power-of-two jumps, and k becomes the remaining item number: each time a block is skipped, its frequency is subtracted from k.

tree.bit[candidate] is a stored Fenwick block, not generally a complete prefix sum. The search skips that block only when the stored frequency is strictly less than the remaining k.

At termination, the search has found the largest prefix length whose sum is strictly less than the original k. That statement describes the finished search, not every intermediate state. The desired item comes immediately after that prefix. Because public positions are zero-based, that prefix length is also the item’s position, so we return index directly.

For the frequencies [2, 0, 3, 1] and original k = 3:

1. Try step 4: the candidate block contains 6 items, so do not skip it.
2. Try step 2: the candidate block contains 2 items, so skip it; index = 2, remaining k = 1.
3. Try step 1: the next candidate block contains 3 items, so do not skip it.
4. Return public position 2.

Walking those blocks directly takes O(log n) steps. Binary-searching positions, with a separate O(log n) prefix query at each step, takes O(log² n) steps.

The Important Restriction: Nonnegative Frequencies

Ordinary sum queries support negative values.

This search requires nonnegative underlying frequencies so that cumulative totals never decrease. With negative values, a prefix could cross the target and later fall below it, invalidating the search logic.

Negative updates are still permitted when removing items, provided the resulting frequency does not become negative.

The function does not scan all values to verify this condition, because doing so would turn a logarithmic operation into a linear one. Maintaining the frequency invariant is the caller’s responsibility.

Range Updates: Difference Arrays and Two Trees

The basic implementation supports:

Change one value.
Query the sum of a range.

Other operation combinations need a different arrangement.

Range Additions and Point Queries

Define a difference array:

D[0] = A[0]
D[i] = A[i] - A[i - 1]

Then:

A[i] = D[0] + D[1] + ... + D[i]

Adding delta to every element in [left, right) changes only the difference-array boundaries:

D[left]  += delta
D[right] -= delta    when right < n

Valid intervals satisfy 0 <= left <= right <= n. After those bounds are checked, an empty interval is a no-op, including [n, n). When right == n, omit the right-boundary difference update because it lies outside the array.

A Fenwick tree over D therefore supports range additions through one or two point updates. Querying an individual A[i] becomes a prefix query over D.

Range Additions and Range-Sum Queries

To support both efficiently, maintain two Fenwick trees:

B1 stores D[j].
B2 stores j * D[j].

For the first r elements, every sum below is over 0 <= j < r:

A[0] + ... + A[r - 1]
    = sum((r - j) * D[j] for j in range(r))
    = r * sum(D[j] for j in range(r)) - sum(j * D[j] for j in range(r))
    = r * B1.prefix_sum(r) - B2.prefix_sum(r)

Each D[j] contributes to exactly r - j elements in that prefix. The second tree corrects for how many positions each difference contributes to. This is an algebraic extension of the sum structure, not a generic solution for every kind of range update.

Operation Combinations and Trade-offs

Lazy segment trees support range transformations and interval aggregation under explicit composition rules. They are the more general option—not an automatic improvement when ordinary sum operations are all you need.

Important Limitations and Nuances

You Cannot Simply Replace Addition With Any Operation

Range sums work because subtraction can remove the contribution of an earlier prefix:

prefix_sum(right) - prefix_sum(left)

Minimum does not have an equivalent inverse.

For example:

Array A: [1, 5]
Array B: [1, 100]

Both have:

Minimum of the first element = 1
Minimum of both elements     = 1

Yet their second elements differ. Those two prefix minima do not contain enough information to recover the minimum of the remaining range.

Specialized Fenwick variants can maintain prefix minima under restricted updates—for example, when values only decrease. That does not make them general-purpose range-minimum structures.

For arbitrary point assignments combined with range minimum, maximum, or other suitable associative aggregations, a segment tree is usually the clearer choice.

The Array Length Does Not Need to Be a Power of Two

The implementation works for lengths such as 5, 13, or 1,000.

Only individual stored blocks have power-of-two lengths. The overall array can have any nonnegative length.

The Standard Dense Structure Assumes Stable Positions

Changing a value is straightforward. Inserting a new element in the middle of a sequence shifts later positions and is a different problem.

Even appending requires care: a newly created Fenwick entry may need to include earlier values in its block. Simply extending the backing array with zero and updating the new position is not a correct general resizing strategy.

For frequently changing ordered keys or arbitrary sequence insertions, consider an augmented balanced tree or another structure designed for that operation.

Memory Is Linear, but Representation Matters

The implementation stores n + 1 aggregate entries and does not retain a separate copy of every current input value.

That is O(n) storage, but an entry in a Python list is not automatically a packed eight-byte integer. Actual memory depends on the language, container, and numeric representation.

Likewise, the logarithmic complexity discussion assumes arithmetic is effectively constant time. Python integers have unlimited precision and can grow beyond machine-word size (Python documentation: numeric types), so extremely large totals introduce additional arithmetic costs.

Read-Only Queries Are Not Automatically Thread-Safe

A query does not mutate the tree, but one logical update modifies several entries. Concurrent access can expose a partially applied update. When operations can execute concurrently, such as from multiple threads, protect complete updates and queries that require a consistent view. For ordinary integer inputs, these synchronous methods contain no suspension point. Ordinary tasks on one asyncio event-loop thread do not interleave halfway through these method calls: a running task continues until it executes an await (Python documentation: asyncio concurrency and multithreading). A larger asynchronous workflow can still need coordination when it yields between operations or accesses the tree through threads.

A Fenwick tree is an aggregation structure, not a transaction or consistency mechanism.

Two-Dimensional Versions Exist

The same idea can be extended across rows and columns to maintain changing grid totals. A straightforward dense version uses nested traversals, giving O(log R × log C) updates and rectangle queries with O(RC) storage.

Sparse variants add coordinate-management complexity. For example, KACTL’s compressed two-dimensional implementation requires the update coordinates to be registered before initialization.

Common Pitfalls and Fixes

Testing the Implementation

A useful test suite should compare the tree against an ordinary array after mixed updates and queries—not only verify a few positive-number examples.

For example:

tree = FenwickTree([3, -2, 5])

assert tree.prefix_sum(0) == 0
assert tree.range_sum(0, 3) == 6
assert tree.range_sum(1, 1) == 0

before = tree.bit.copy()
assert tree.range_sum(1, 3) == 3
assert tree.bit == before  # Queries must not change stored sums.

tree.add(1, -4)
assert tree.range_sum(0, 3) == 2

tree.set(0, 10)
assert tree.range_sum(0, 3) == 9

The implementations shown above, a two-tree range-addition example, and a deterministic test suite are in fenwick-tree-examples.py. The tests check construction, updates, and queries against an ordinary array; frequency selection and inversion counting against direct counts; and the two-tree formula after range additions, including empty intervals and a right endpoint of n. These are correctness tests, not performance benchmarks.

Conclusion

A Fenwick tree is a compact answer to a specific problem: maintaining cumulative totals while individual values change.

Its efficiency comes from storing carefully selected blocks and navigating them through the binary representation of their indices. The query walks through disjoint blocks that form a prefix. The update walks through containing blocks that must change.

The practical decision is straightforward: keep a plain array when queries are rare, use prefix sums when data is static, choose a Fenwick tree for interleaved sum queries and point updates, and move to a more general structure when the required operations demand it.

The most important part is not memorizing i & -i. It is understanding which range each stored entry represents—and why the next index is the correct one.

Key Takeaways

• Queries read; updates write. Changing the local query index does not mutate the tree.
• The API contract matters. Keep indexing conventions, range endpoints, and addition-versus-assignment semantics explicit.
• Choose the structure for the operations. Fenwick trees are excellent for mutable sums and frequencies, but not a universal replacement for prefix arrays or segment trees.