Fenwick tree (Binary Indexed Tree)

You are maintaining a list of numbers and must answer two kinds of operations: update one number, and find the sum of a range. A plain prefix-sum array answers a range query in O(1), but a single update forces you to recompute every prefix sum after it, which costs O(n) per update. A Fenwick tree, also called a binary indexed tree, keeps both operations at O(log n).

It stores the data as a single array, but each position covers a range of elements rather than a single one, and the ranges overlap according to the binary representation of the index. Updating one element or querying a range moves through only O(log n) positions instead of scanning the whole array, by following jumps that bit manipulation computes directly.

Storing partial sums by range, not by prefix

A prefix-sum array stores, at position i, the sum of elements 0 through i. Reading a range from that is fast, but a single update forces every later position to be recomputed.

A Fenwick tree stores something narrower at each position: the sum of a range that ends there, whose length is fixed by the position's lowest set bit. For an array of 8 elements indexed 0 through 7, here is what each tree position covers:

• Position 1 (binary 0001) covers just element 0, the sum of [0, 0].
• Position 2 (binary 0010) covers elements 0 and 1, the sum of [0, 1].
• Position 3 (binary 0011) covers just element 2, the sum of [2, 2].
• Position 4 (binary 0100) covers elements 0 through 3, the sum of [0, 3].
• Position 5 (binary 0101) covers just element 4, the sum of [4, 4].
• Position 6 (binary 0110) covers elements 4 and 5, the sum of [4, 5].
• Position 7 (binary 0111) covers just element 6, the sum of [6, 6].
• Position 8 (binary 1000) covers elements 0 through 7, the sum of [0, 7].

The range length always equals the position's lowest set bit. The expression i & -i extracts it directly: 6 is 0110 in binary, and its negation in two's complement is 1010. The bitwise AND of the two is 0010, which is 2, matching position 6's coverage of exactly 2 elements.

Building the tree

Start with a tree array of zeros, one entry longer than the input array since positions are 1-indexed. For each element, add its value at the corresponding tree position, then move to the next position that also needs it: i + (i & -i). Repeat until that position runs past the end of the array.

Each position only feeds the range one level above it, the same way each node in a tree passes information to its parent, so a single update touches at most O(log n) positions on its way up.

Querying a range sum

To find the sum from index 0 to index i (0-indexed), start at tree position i + 1 and walk backward, subtracting the lowest set bit each time: i := i - (i & -i). Add up every tree value you pass through along the way. When the position reaches 0, the values you collected add up to the sum from 0 to i.

A range query from L to R is sum(0, R) - sum(0, L - 1), the same subtraction you would use with an ordinary prefix-sum array.

Building and querying a concrete tree

Take the array [3, 2, 1, 4, 5, 1, 2, 3], with 1-indexed tree positions 1 through 8 lined up against elements 0 through 7. After building, the tree holds: position 1 stores 3 (element 0), position 2 stores 5 (elements 0-1), position 3 stores 1 (element 2), position 4 stores 10 (elements 0-3), position 5 stores 5 (element 4), position 6 stores 6 (elements 4-5), position 7 stores 2 (element 6), and position 8 stores 21 (elements 0-7).

To query the sum from 0 to 4, which should be 3 + 2 + 1 + 4 + 5 = 15, start at position 5 (index 4 plus 1). Add tree[5] = 5, then move to 5 - (5 & -5) = 5 - 1 = 4. Add tree[4] = 10, then move to 4 - (4 & -4) = 4 - 4 = 0, which stops the walk. The total is 5 + 10 = 15, matching the expected sum.

1import sys2
3
4def main() -> None:5    data = sys.stdin.read().split()6    if not data:7        return8
9    n = int(data[0])10    arr = list(map(int, data[1:n + 1]))11
12    # Build Fenwick tree (1-indexed)13    tree = [0] * (n + 1)14
15    def update(idx, val):16        # idx is 1-indexed17        while idx <= n:18            tree[idx] += val19            idx += idx & -idx20
21    # Initialize tree with array elements22    for i in range(n):23        update(i + 1, arr[i])24
25    def query(idx):26        # Sum from 0 to idx (0-indexed), converted to 1-indexed query27        idx += 1  # Convert to 1-indexed28        s = 029        while idx > 0:30            s += tree[idx]31            idx -= idx & -idx32        return s33
34    # Query from 0 to 4 (should be 3+2+1+4+5=15)35    print(f"Sum [0, 4]: {query(4)}")36
37    # Query from 0 to 7 (should be 3+2+1+4+5+1+2+3=21)38    print(f"Sum [0, 7]: {query(7)}")39
40    # Update element at index 2 from 1 to 6 (add 5)41    update(3, 5)42
43    # Query again44    print(f"After update, sum [0, 4]: {query(4)}")45    print(f"After update, sum [0, 7]: {query(7)}")46
47
48if __name__ == "__main__":49    main()

8 3 2 1 4 5 1 2 3

Sum [0, 4]: 15
Sum [0, 7]: 21
After update, sum [0, 4]: 20
After update, sum [0, 7]: 26

The program queries [0, 4] and [0, 7] first, printing 15 and 21. Then it updates element 2 (1-indexed position 3) by adding 5, the difference between its old value of 1 and its new value of 6. That update walks position 3, then 3 + (3 & -3) = 4, then 4 + 4 = 8, then 8 + 8 = 16, which is past the end of the tree, so the walk stops there. Every position the update touched, 3, 4, and 8, now carries the extra 5, so the next two queries return 20 and 26, each 5 more than before.

Common mistakes

Mixing up 0-indexed and 1-indexed logic is the most common error. A Fenwick tree works most naturally with 1-indexed positions, with tree[0] left unused. If the input array is 0-indexed but the tree is 1-indexed, keep that offset applied consistently at every update and query, or the sums will be off by one element.

Reversing the bit trick's direction is another. i & -i gives the lowest set bit; adding it moves toward the position's parent during an update, and subtracting it moves down through the covering ranges during a query. Swap the direction in either operation, and the tree still runs without crashing, but every sum it returns is wrong.

A third mistake is updating with the element's new value instead of the difference from its old value. The tree only ever adds; if you want to set an element to a new value, first read its current value, then apply the update with the difference between new and old, exactly as the update to position 3 above added 5, not 6.

Recap

A Fenwick tree stores a set of overlapping partial sums in a single array, indexed so that each position's lowest set bit fixes the length of the range it covers. Updates walk upward by adding the lowest set bit, and queries walk downward by subtracting it, both in O(log n) steps. When updates are frequent enough that recomputing prefix sums from scratch is too slow, a Fenwick tree keeps both operations fast.