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.

The Dumbest Way to Build a BIT (and Why You Should Care)

Most tutorials shove the add() loop inside a for loop and call it a day. O(n log n) construction. Fine for n=1000. In production, you're processing millions of elements. That extra log factor kills you cold.

Here's the insight: every index i in the BIT must store the sum of a contiguous range ending at i. The standard construction adds each element via point update — that's O(n log n). But you can build it in O(n) by exploiting the same parent-reversal logic you use in queries.

Walk through the array once. For each index i, add arr[i] to bit[i]. Then immediately propagate that value to the next responsible index: j = i + (i & -i). If j ≤ n, add bit[i] to bit[j]. No nested loops. No repeated calls to add(). Just a single pass with direct responsibility transfer.

This isn't an academic trick. When you're processing streaming data or building prefix-sum structures for competitive programming timers, this is the difference between passing and timeout.

// io.thecodeforge — dsa tutorial

public class LinearBitBuild {
    public static int[] buildFenwick(int[] arr) {
        int n = arr.length;
        int[] bit = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            bit[i] += arr[i - 1];
            int j = i + (i & -i);
            if (j <= n) {
                bit[j] += bit[i];
            }
        }
        return bit;
    }

    public static void main(String[] args) {
        int[] input = {3, 1, 4, 1, 5, 9};
        int[] bit = buildFenwick(input);
        for (int i = 1; i <= input.length; i++) {
            System.out.print(bit[i] + " ");
        }
    }
}

Range Update, Range Query Without the Segment Tree Bloat

Segment trees handle range updates and range queries. They also require four times the memory and twice the code. If you're building a leaderboard, a inventory tracker, or any system that applies constant deltas to ranges and reads totals, you want a lazy difference BIT.

Technique: maintain two BITs. BIT1 tracks base increments — same as a difference array. BIT2 tracks the scaled prefix of those increments. Why two? Because a range update [l, r] by value v produces a query-time correction proportional to the index.

This works because the correction term sum(BIT2, p) accounts for the fact that earlier updates should apply fully, while later ones only partially. Memory: 2n+2 integers. Code: ~20 lines. Production: battle-tested in codeforces round 1700+.

// io.thecodeforge — dsa tutorial

public class RangeUpdateRangeQuery {
    static long[] bit1, bit2;
    static int n;

    static void add(long[] bit, int i, long v) {
        while (i <= n) {
            bit[i] += v;
            i += i & -i;
        }
    }

    static long sum(long[] bit, int i) {
        long s = 0;
        while (i > 0) {
            s += bit[i];
            i -= i & -i;
        }
        return s;
    }

    static void rangeUpdate(int l, int r, long v) {
        add(bit1, l, v);
        add(bit1, r + 1, -v);
        add(bit2, l, v * (l - 1));
        add(bit2, r + 1, -v * r);
    }

    static long prefixSum(int p) {
        return sum(bit1, p) * p - sum(bit2, p);
    }

    public static void main(String[] args) {
        n = 5;
        bit1 = new long[n + 2];
        bit2 = new long[n + 2];
        rangeUpdate(2, 4, 10);
        System.out.println(prefixSum(3)); // expected 10
        System.out.println(prefixSum(5)); // expected 20
    }
}

Conceptual Explanation

Fenwick Trees (BIT) solve one problem really well: dynamic prefix sums. Unlike arrays (O(1) update, O(n) query) or segment trees (heavy structure), BIT balances updates and queries at O(log n). The core idea is that each index stores the sum of a range of elements, where the range size is determined by the least significant bit (LSB) of the index. To update, you walk upward adding to indices whose LSB cascades, covering your element. To query, you walk downward, adding partial ranges until index hits zero. This works because every integer can be uniquely decomposed into powers of two, which matches the tree structure. The index is 1-based internally to avoid infinite loops. The WHY: we trade memory (O(n)) for speed, and we exploit binary representation to avoid recursion or complex parent-child logic. This makes BITs ideal for cumulative frequency tables, inversion counts, and online queries where the data changes.

// io.thecodeforge — dsa tutorial
class Fenwick {
    int n;
    int[] bit;
    public Fenwick(int n) {
        this.n = n;
        bit = new int[n + 1];
    }
    void add(int i, int delta) {
        while (i <= n) {
            bit[i] += delta;
            i += i & -i;
        }
    }
    int sum(int i) {
        int s = 0;
        while (i > 0) {
            s += bit[i];
            i -= i & -i;
        }
        return s;
    }
}

Output

For a typical Fenwick Tree tutorial, output examples clarify the internal state and query results. Consider building a BIT from array [1, 2, 3, 4] and querying prefix sums: sum(1)=1, sum(2)=3, sum(3)=6, sum(4)=10. The tree stores values as: bit[1]=1, bit[2]=3, bit[3]=3, bit[4]=10. If we update index 2 by +5, we add 5 to bit[2] and bit[4], yielding bit[2]=8, bit[4]=15. After update, sum(2)=1+8=9, sum(4)=1+8+3+? Actually fixed: sum(4)=bit[4]=15. The output from the counting inversions application: given array [3,1,2], Fenwick helps count pairs (i<j, arr[i]>arr[j]): process right to left, query prefix sum of smaller elements, update each — final inversions=2. Output these intermediate sums to verify correctness: after processing 2, query=0; after 1, query=1; after 3, query=2. These concrete outputs help debug and solidify understanding of how BIT accumulates frequencies.

// io.thecodeforge — dsa tutorial
public class Main {
    public static void main(String[] args) {
        Fenwick ft = new Fenwick(4);
        for (int i = 1; i <= 4; i++) ft.add(i, i);
        for (int i = 1; i <= 4; i++)
            System.out.println("sum(" + i + ")=" + ft.sum(i));
        ft.add(2, 5);
        System.out.println("After update:");
        for (int i = 1; i <= 4; i++)
            System.out.println("sum(" + i + ")=" + ft.sum(i));
    }
} // Output: sum(1)=1 sum(2)=3 sum(3)=6 sum(4)=10 then ...=1,8,11,15