Fenwick Tree — Delta vs Absolute Update Bug Corrupts Sums

Competitive programmers love Fenwick Trees because they solve a brutally common problem — range prefix-sum queries with point updates — in O(log n) time AND O(n) space, with constants so small the code fits in about 10 lines. You'll find them inside database engines for order-book aggregations, in game servers tracking cumulative scores, and in every serious competitive programming solution that involves frequency arrays or inversions. If you've ever hit a TLE on a naive cumulative-sum approach, a Fenwick Tree is likely the fix.

The core problem is this: you have an array of numbers that changes over time, and you need to repeatedly answer 'what is the sum of elements from index 1 to index k?' A flat prefix-sum array answers queries in O(1) but updates in O(n). A Fenwick Tree gives you O(log n) for both, with a constant factor that is almost embarrassingly small — often 3-5x faster in wall-clock time than a segment tree for the same problem.

By the end of this article you'll understand exactly why the bit-manipulation trick i += i & (-i) works, how to extend the tree for range updates and point queries, how to do a binary search on the tree itself, and the exact production bugs that bite engineers the first time they ship this structure in real code.

What is a Fenwick Tree? — Plain English

A Fenwick Tree (also called Binary Indexed Tree or BIT) is a data structure that answers the question 'what is the sum of elements from index 1 to i?' in O(log n) time, while also allowing you to update any element in O(log n) time. A naive array handles point updates in O(1) but prefix sums in O(n). A prefix sum array handles queries in O(1) but updates in O(n). A Fenwick tree strikes the middle — O(log n) for both. The trick is that each node in the BIT stores the sum of a specific range of elements, and the range size is determined by the lowest set bit of the node's index. For example, index 6 (binary 110) has lowest bit 2, so it stores the sum of 2 elements: arr[5]+arr[6].

class FenwickTree:
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def update(self, i, delta):
        while i <= self.n:
            self.bit[i] += delta
            i += i & (-i)

    def query(self, i):
        total = 0
        while i > 0:
            total += self.bit[i]
            i -= i & (-i)
        return total

How Fenwick Tree Works — Step by Step

Building and querying a BIT on arr=[1,3,5,7,9,11] (1-indexed, n=6):

Update(i, delta): add delta to BIT[i], then move to the next responsible node by adding the lowest set bit of i. 1. update(3, 5): BIT[3] += 5, then 3+(3&-3)=3+1=4 → BIT[4] += 5, then 4+4=8 > n, stop.

Query(i): sum from 1 to i by traversing upward removing the lowest set bit. 1. query(6): sum += BIT[6]; 6-(6&-6)=6-2=4 → sum += BIT[4]; 4-4=0 → stop. Sum = BIT[6]+BIT[4]. 2. BIT[6] covers arr[5]+arr[6]=9+11=20; BIT[4] covers arr[1]+arr[2]+arr[3]+arr[4]=1+3+5+7=16. Total=36.

Range query(l,r) = query(r) - query(l-1).

Fenwick Tree Node Responsibilities — Which Indices Each Node Covers

Each node in a Fenwick Tree is responsible for a contiguous range of the original array. The range length is equal to the lowest set bit (LSB) of the node's index. The range starts at i - (i & -i) + 1 and ends at i. Here is a visual mapping for the first 8 indices:

• Index 1 (binary 1): LSB=1 → covers arr[1] (range length 1)
• Index 2 (binary 10): LSB=2 → covers arr[1..2] (length 2)
• Index 3 (binary 11): LSB=1 → covers arr[3] (length 1)
• Index 4 (binary 100): LSB=4 → covers arr[1..4] (length 4)
• Index 5 (binary 101): LSB=1 → covers arr[5] (length 1)
• Index 6 (binary 110): LSB=2 → covers arr[5..6] (length 2)
• Index 7 (binary 111): LSB=1 → covers arr[7] (length 1)
• Index 8 (binary 1000): LSB=8 → covers arr[1..8] (length 8)

The tree structure is implicit: the parent of index i is i + (i & -i). The child for querying (in the reverse direction) is i - (i & -i).

Worked Example — Tracing BIT Construction

Build BIT for arr=[1,3,5,7,9,11] (1-indexed).

Initialize BIT=[0,0,0,0,0,0,0] (index 0 unused).

update(1,1): BIT[1]+=1 → BIT[1]=1. 1+(1&-1)=1+1=2 → BIT[2]+=1 → BIT[2]=1. 2+2=4 → BIT[4]+=1=1. 4+4=8>6, stop. update(2,3): BIT[2]+=3=4. 2+2=4 → BIT[4]+=3=4. 8>6 stop. update(3,5): BIT[3]+=5=5. 3+1=4 → BIT[4]+=5=9. 8>6 stop. update(4,7): BIT[4]+=7=16. 4+4=8>6 stop. update(5,9): BIT[5]+=9=9. 5+1=6 → BIT[6]+=9=9. 6+2=8>6 stop. update(6,11): BIT[6]+=11=20. 6+2=8>6 stop.

Final BIT=[0,1,4,5,16,9,20]. query(6): BIT[6]=20; 6-2=4; BIT[4]=16; 4-4=0 stop. Sum=36. Correct (1+3+5+7+9+11=36).

C++ Implementation of Fenwick Tree

In C++, the Fenwick Tree implementation follows the same logic as Python but requires manual memory management or use of std::vector. The 1-indexed convention is critical. Below is a complete template class that supports point update and prefix sum query. Note that the array size is n+1 (index 0 unused). The bit manipulation i & -i works identically in C++ as in Python because integers are two's complement on all modern platforms.

#include <vector>

class FenwickTree {
public:
    FenwickTree(int n) : bit(n + 1, 0) {}

    void update(int i, int delta) {
        while (i < (int)bit.size()) {
            bit[i] += delta;
            i += i & -i;
        }
    }

    int query(int i) {
        int sum = 0;
        while (i > 0) {
            sum += bit[i];
            i -= i & -i;
        }
        return sum;
    }

private:
    std::vector<int> bit;
};

// Example usage
// FenwickTree ft(10);
// ft.update(3, 5);
// printf("%d\n", ft.query(3)); // 5

Advantages and Disadvantages of Fenwick Tree

Fenwick Trees offer a sweet spot between simplicity and performance for prefix-sum problems with point updates. However, they are not a universal tool. Understanding their strengths and weaknesses helps you decide when to use them vs. a segment tree or other structures.

Fenwick Tree for Range Updates and Point Queries — The Difference BIT

Sometimes you need to add a value to every element in a range [l, r], and then later query the current value at a single point. A standard BIT doesn't support range updates directly, but with a 'difference BIT' you can do it in O(log n).

Create a BIT that stores differences. To add delta to all elements in [l, r], perform two point updates: - update(l, +delta) - update(r+1, -delta)

Then the point query at index i is simply query(i) — the prefix sum of the difference array gives the current value at i. This works because a prefix sum of differences reconstructs the original value.

Example: arr initially [0,0,0,0,0]. Add 5 to indices [2,3]: update(2,5), update(4,-5). Query(3) = BIT[3] =? Let's trace: BIT after updates... actually the prefix sum query(3) = sum of diffs up to index 3 = BIT[3] + BIT[2]? But careful with the BIT structure. The standard difference BIT still works: the BIT stores the difference array values, and point query is just prefix sum of that difference array. So query(i) gives diff[1] + diff[2] + ... + diff[i], which equals the cumulative change up to i, which gives the original value if the original array was zero. For non-zero initial values, you add initial arr[i] to query(i).

class RangeUpdateBIT:
    def __init__(self, n):
        self.bit = FenwickTree(n)

    def range_add(self, l, r, delta):
        # Add delta to all elements in [l, r]
        self.bit.update(l, delta)
        self.bit.update(r+1, -delta)

    def get_point(self, i):
        # Get current value at position i
        return self.bit.query(i)

# Example
bit = RangeUpdateBIT(10)
bit.range_add(2, 5, 10)  # Add 10 to indices 2..5
print(bit.get_point(3))   # 10
print(bit.get_point(1))   # 0
print(bit.get_point(6))   # 0

2D Fenwick Tree — Sum Over Subrectangle

A 2D Fenwick Tree extends the concept to a matrix. It supports point update at (x, y) and prefix sum query from (1,1) to (x,y) in O(log n log m) time and O(n m) memory. The key is to nest BIT logic: each row contains a BIT, and rows themselves are organized in a BIT-like structure. Updates propagate both horizontally and vertically.

Implementation: maintain a 2D BIT array bit[x][y] where each row x has a BIT that stores column contributions. To update (x, y) with delta, iterate rows using while (x <= n) { update_row(x, y, delta); x += x & -x; }. In update_row, iterate columns using while (y <= m) { bit[x][y] += delta; y += y & -y; }. Prefix sum query does the same in reverse.

Example problem: Given a grid of numbers, answer queries that ask for sum of a subrectangle, with point updates. This is a classic problem in competitive programming and can be solved with a 2D BIT when the grid size is moderate (e.g., 1000x1000). For larger grids, consider a prefix sum approach if no updates, or a segment tree of segment trees.

Coordinate compression: If the grid dimensions are large but sparse (few updates), compress coordinates. Create a list of all x and y that appear in updates and queries, sort and deduplicate, then map coordinates to compressed indices for the BIT.

Production insight: In geospatial applications (e.g., aggregating sensor readings over a region), a 2D BIT can provide real-time rectangle sum queries. However, the memory cost is O(n*m), which can be prohibitive for large grids. Consider using a sparse matrix representation or KD-tree for massive datasets.

class Fenwick2D:
    def __init__(self, n, m):
        self.n = n
        self.m = m
        self.bit = [[0]*(m+1) for _ in range(n+1)]

    def update(self, x, y, delta):
        i = x
        while i <= self.n:
            j = y
            while j <= self.m:
                self.bit[i][j] += delta
                j += j & -j
            i += i & -i

    def query(self, x, y):
        total = 0
        i = x
        while i > 0:
            j = y
            while j > 0:
                total += self.bit[i][j]
                j -= j & -j
            i -= i & -i
        return total

    def range_sum(self, x1, y1, x2, y2):
        # inclusive rectangle sum
        return (self.query(x2, y2) - self.query(x1-1, y2)
                - self.query(x2, y1-1) + self.query(x1-1, y1-1))

# Example
ft2d = Fenwick2D(5, 5)
ft2d.update(2, 3, 7)
ft2d.update(4, 2, 3)
print(ft2d.range_sum(1, 1, 5, 5))  # 10

Binary Search on Fenwick Tree — Finding Prefix Index by Sum

Sometimes you need to find the smallest index i such that prefix_sum(i) >= K. A naive approach does O(log^2 n) by binary searching over index and calling query each time. But because BIT supports logarithmic query, you can do better — O(log n) using the tree itself, leveraging the structure of indices.

You start at 0 and consider the highest power of two <= n. If adding that index to your current position keeps the sum below K, you add it and move to that index. Then divide the step by 2 and repeat. This is analogous to binary lifting.

Implementation: maintain pos = 0 and step = highestPowerOfTwo(n). While step > 0: - test = pos + step - if test <= n and bit[test] + current_sum < K: pos = test; current_sum += bit[test] - step >>= 1 At the end, answer = pos+1 (the next index).

This technique is used in order statistics trees (finding k-th smallest element) and in compressing frequency arrays for rank queries.

Application: Counting Inversions with Fenwick Tree

An inversion in an array is a pair (i, j) such that i < j and arr[i] > arr[j]. Counting inversions is a classic problem that can be solved with a Fenwick Tree in O(n log n) time. The idea: traverse the array from left to right, and for each element, query how many elements greater than it have already been seen. The BIT stores frequency of values. However, values can be large, so we first compress them to ranks (1..n). Then, for each element x (after compression), we add 1 to its rank in BIT, and query the sum of ranks greater than x (i.e., n - query(x)).

Worked example: arr = [3, 1, 2] 1. Compress to ranks: sorted unique = [1,2,3] -> map: 3->3, 1->1, 2->2. Compressed array: [3,1,2]. 2. Initialize BIT of size 3 with zeros. 3. Process each element: - i=0, x=3: query(3) = 0 (prefix sum up to 3). Inversions added = total processed (0) - query(3) = 0. Update BIT[3] += 1. - i=1, x=1: query(1) = 0. Inversions = 1 - 0 = 1 (because element 3 > 1). Update BIT[1] += 1. - i=2, x=2: query(2) = BIT[1]+BIT[2] = 1+0=1. Inversions = 2 - 1 = 1 (since element 3 > 2). Update BIT[2] += 1. 4. Total inversions = 0+1+1 = 2.

Manually verify: pairs (3,1), (3,2) -> 2 inversions. Correct.

The code compresses values to ranks and uses the standard BIT. This approach is widely used in competitive programming.

def count_inversions(arr):
    # coordinate compression
    sorted_unique = sorted(set(arr))
    rank = {v: i+1 for i, v in enumerate(sorted_unique)}  # 1-indexed
    n = len(sorted_unique)
    bit = FenwickTree(n)
    inversions = 0
    for i, val in enumerate(arr):
        r = rank[val]
        bit.update(r, 1)
        # number of elements greater than current = i+1 - query(r)
        inversions += (i+1) - bit.query(r)
    return inversions

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

Practice Problems for Fenwick Tree

Solidify your understanding of Fenwick Tree by solving these problems, ordered from easy to hard. They cover point updates, range queries, difference BIT, binary search, 2D BIT, and inversion count.

1. LeetCode 307 - Range Sum Query - Mutable (Medium): Classic problem to implement BIT for point update and range sum query.
2. - [https://leetcode.com/problems/range-sum-query-mutable/](https://leetcode.com/problems/range-sum-query-mutable/)
3. CSES Problem Set - Range Sum Queries II (Easy): Simple BIT for point update and prefix sum queries.
4. - [https://cses.fi/problemset/task/1648/](https://cses.fi/problemset/task/1648/)
5. CSES Problem Set - Inversions (Easy): Count inversions using BIT.
6. - [https://cses.fi/problemset/task/1748/](https://cses.fi/problemset/task/1748/)
7. CSES Problem Set - Forest Queries II (Medium): 2D BIT on a grid with point updates.
8. - [https://cses.fi/problemset/task/1652/](https://cses.fi/problemset/task/1652/)
9. Codeforces 1354D - Multiset (Medium): Order statistics using BIT binary search to find k-th smallest element.
10. - [https://codeforces.com/problemset/problem/1354/D](https://codeforces.com/problemset/problem/1354/D)
11. Codeforces 1191C - Tokitsukaze and Discarding Cards (Medium): Difference BIT for range updates.
12. - [https://codeforces.com/problemset/problem/1191/C](https://codeforces.com/problemset/problem/1191/C)
13. SPOJ - KQUERY (Hard): Offline queries using BIT with coordinate compression.
14. - [https://www.spoj.com/problems/KQUERY/](https://www.spoj.com/problems/KQUERY/)

These problems will help you master both basic and advanced BIT techniques.