Fenwick Tree Variants: Range Updates & 2D BIT

                Mastery target: Level B implementation. You should be able to derive the difference-array trick, the dual-BIT range-query formula, and the 2D nested-traversal generalization from the standard Fenwick Tree, and implement all three from memory.
            

1. Introduction & Motivation

The standard Fenwick Tree (Binary Indexed Tree, or BIT) supports two operations in $O(\log n)$: add a value to one position, and read the sum of a prefix. That combination is enough for problems like running totals and order-statistics counting, but many real workloads need the opposite mix, or need it over two dimensions instead of one:

Range-update / point-query: add a value to every position in a range, then ask for the value at a single position. Example: a bulk "add 10 bonus points to everyone ranked 50-100" operation, followed by "what is player 73's score right now?"
Range-update / range-query: add a value to every position in a range, then ask for the sum over another range. Example: repeated "increase sales in these stores" adjustments, followed by "what were total regional sales last quarter?"
2D BIT: the same point-update/prefix-query mechanics, but over a matrix, so a query asks for the sum inside a rectangle. Example: a spreadsheet or heatmap where cells are updated one at a time and the UI must answer arbitrary rectangular sums quickly.

None of these need a new data structure. Each one is the same Fenwick Tree, applied to a transformed array, or applied twice, or nested inside itself along a second axis. That reuse is the whole point of this lesson: once the point-update/prefix-query mechanism is second nature, these variants are small, provable extensions rather than new machinery.

2. Prerequisites

This lesson assumes you already understand the standard, single-purpose Fenwick Tree: 1-indexed storage, the point update(i, delta) that walks i += i & (-i), and the prefix query(i) that walks i -= i & (-i). That mechanism, along with a full worked countSmaller (LeetCode 315) application built from coordinate compression plus a BIT, is covered in the Union-Find, Trie, Fenwick & Segment Tree guide. It is not repeated here — every variant below is built by composing that exact FenwickTree class, unchanged, in a different arrangement.

If the phrase "walk up by adding the lowest set bit, walk down by removing it" does not already feel familiar, read that section first.

3. A Concrete Example

Worked Example

Add 5 to a range, then read individual positions

Start with the 1-indexed array A = [3, 1, 4, 1, 5, 9] (positions 1 through 6). We want to apply add 5 to every position in [2, 4], and then be able to answer "what is the value at position i?" for any i, without ever touching all six positions directly.

The trick is to stop storing the array itself and instead store its difference array $D$, where $D[1] = A[1]$ and $D[j] = A[j] - A[j-1]$ for $j > 1$. A range update of $[l, r]$ by delta becomes exactly two point edits to $D$: add delta at $l$, and subtract delta at $r+1$ (if it exists). Reading $A[i]$ back becomes a prefix sum of $D$ up to $i$, because the prefix sum telescopes: $A[i] = D[1] + D[2] + \cdots + D[i]$.

Position $i$	$D[i]$ before update	Edit applied	$D[i]$ after update	Prefix sum of $D$ up to $i$ (= new $A[i]$)
1	3	—	3	3
2	-2	+5 (start of range)	3	3+3=6
3	3	—	3	6+3=9
4	-3	—	-3	9-3=6
5	4	-5 (one past end of range)	-1	6-1=5
6	4	—	4	5+4=9

The final prefix-sum column reads [3, 6, 9, 6, 5, 9] — exactly A with 5 added to positions 2, 3, and 4, and positions 1, 5, 6 untouched. Every point query only walked $O(\log n)$ tree nodes; the range update only touched two positions of $D$, never all three positions inside $[2,4]$ directly.

4. Core Insight: Range-Update / Point-Query via Difference Array

                Core insight: Store a Fenwick Tree over the difference array $D$ instead of over $A$ directly. A range update [l, r] += delta is two point updates on the same underlying FenwickTree you already know: update(l, +delta) and update(r+1, -delta). A point query for $A[i]$ is exactly query(i) — the ordinary prefix-sum query — run against the difference-array BIT.
            

To seed the structure with a non-zero starting array, treat every initial value as its own trivial range update: for each $i$ from 1 to $n$, call range_update(i, i, A[i]). Because $l = r = i$, this only ever touches $D[i]$ and $D[i+1]$, so seeding the whole array costs $O(n \log n)$ and is correct by the same telescoping argument used above.

class FenwickTree:
    """The standard point-update / prefix-query BIT (unchanged)."""
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)

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

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


class RangeUpdatePointQueryBIT:
    """
    Range-add, point-read, both O(log n), built by running a
    FenwickTree over the array's difference array instead of the
    array itself.
    """
    def __init__(self, n):
        self.n = n
        self.bit = FenwickTree(n)

    def range_update(self, l, r, delta):
        """Add delta to every position in [l, r] (1-indexed, inclusive)."""
        self.bit.update(l, delta)
        if r + 1 <= self.n:
            self.bit.update(r + 1, -delta)

    def point_query(self, i):
        """Current value at position i (1-indexed)."""
        return self.bit.query(i)

    def build(self, values):
        """Seed with a 1-indexed-style list where values[0] is unused,
        or a 0-indexed list of length n mapped to positions 1..n."""
        for i in range(1, self.n + 1):
            self.range_update(i, i, values[i - 1])


# Same numbers as the worked example: A = [3, 1, 4, 1, 5, 9]
ruq = RangeUpdatePointQueryBIT(6)
ruq.build([3, 1, 4, 1, 5, 9])
ruq.range_update(2, 4, 5)
print([ruq.point_query(i) for i in range(1, 7)])  # [3, 6, 9, 6, 5, 9]

// Range-update / point-query BIT via a difference-array FenwickTree
#include <iostream>
#include <vector>
using namespace std;

class FenwickTree {
    vector<long long> tree;
    int n;
public:
    FenwickTree(int n) : n(n), tree(n + 1, 0) {}

    void update(int i, long long delta) {
        for (; i <= n; i += i & (-i))
            tree[i] += delta;
    }

    long long query(int i) {
        long long s = 0;
        for (; i > 0; i -= i & (-i))
            s += tree[i];
        return s;
    }
};

class RangeUpdatePointQueryBIT {
    FenwickTree bit;
    int n;
public:
    RangeUpdatePointQueryBIT(int n) : bit(n), n(n) {}

    void rangeUpdate(int l, int r, long long delta) {
        bit.update(l, delta);
        if (r + 1 <= n) bit.update(r + 1, -delta);
    }

    long long pointQuery(int i) {
        return bit.query(i);
    }

    void build(const vector<long long>& values) {
        for (int i = 1; i <= n; i++)
            rangeUpdate(i, i, values[i - 1]);
    }
};

int main() {
    RangeUpdatePointQueryBIT ruq(6);
    ruq.build({3, 1, 4, 1, 5, 9});
    ruq.rangeUpdate(2, 4, 5);
    for (int i = 1; i <= 6; i++)
        cout << ruq.pointQuery(i) << " ";  // 3 6 9 6 5 9
    cout << endl;
}

// Range-update / point-query BIT via a difference-array FenwickTree
import java.util.*;

class FenwickTree {
    long[] tree;
    int n;

    FenwickTree(int n) {
        this.n = n;
        tree = new long[n + 1];
    }

    void update(int i, long delta) {
        for (; i <= n; i += i & (-i))
            tree[i] += delta;
    }

    long query(int i) {
        long s = 0;
        for (; i > 0; i -= i & (-i))
            s += tree[i];
        return s;
    }
}

class RangeUpdatePointQueryBIT {
    FenwickTree bit;
    int n;

    RangeUpdatePointQueryBIT(int n) {
        this.n = n;
        bit = new FenwickTree(n);
    }

    void rangeUpdate(int l, int r, long delta) {
        bit.update(l, delta);
        if (r + 1 <= n) bit.update(r + 1, -delta);
    }

    long pointQuery(int i) {
        return bit.query(i);
    }

    void build(long[] values) {
        for (int i = 1; i <= n; i++)
            rangeUpdate(i, i, values[i - 1]);
    }
}

public class RangeUpdatePointQueryDemo {
    public static void main(String[] args) {
        RangeUpdatePointQueryBIT ruq = new RangeUpdatePointQueryBIT(6);
        ruq.build(new long[]{3, 1, 4, 1, 5, 9});
        ruq.rangeUpdate(2, 4, 5);
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= 6; i++) sb.append(ruq.pointQuery(i)).append(" ");
        System.out.println(sb.toString().trim());  // 3 6 9 6 5 9
    }
}

5. Core Insight: Range-Update / Range-Query via Dual BIT

                Core insight: One difference-array BIT gives fast point reads but not fast range sums, because $\sum_{k=l}^{r} A[k]$ still needs prefix sums of the original array, not just of $D$. The fix is to keep a second BIT alongside the first, so that the original array's prefix sum can be reconstructed algebraically from the two of them, without ever materializing $A$ itself.
            

Deriving the formula

As before, let $D$ be the difference array of $A$, so $A[k] = \sum_{j=1}^{k} D[j]$. Expand the prefix sum of $A$ by swapping the order of summation:

$$\text{prefix}(i) = \sum_{k=1}^{i} A[k] = \sum_{k=1}^{i}\sum_{j=1}^{k} D[j] = \sum_{j=1}^{i} D[j]\,(i-j+1)$$

because $D[j]$ contributes to every $A[k]$ with $k \ge j$, and there are exactly $i-j+1$ such $k$ in the range $[j, i]$. Splitting the factor $(i - j + 1) = i - (j-1)$ gives:

$$\text{prefix}(i) = i\sum_{j=1}^{i} D[j] \;-\; \sum_{j=1}^{i} D[j]\,(j-1)$$

Both sums on the right are themselves prefix sums, so each can be answered by its own ordinary Fenwick Tree:

$B_1$ is a FenwickTree over $D$ itself — identical to the range-update/point-query variant above.
$B_2$ is a FenwickTree over the index-weighted difference $D[j]\,(j-1)$.

giving the closed form $\;\text{prefix}(i) = i \cdot B_1.\text{query}(i) - B_2.\text{query}(i)$. A range update [l, r] += delta still edits only two positions, but now on both BITs: at position $l$ it adds delta to $B_1$ and delta*(l-1) to $B_2$; at position $r+1$ it adds -delta to $B_1$ and -delta*r to $B_2$ (since the weight at index $r+1$ is $(r+1)-1=r$). A range sum is then just prefix(r) - prefix(l-1).

Checking this against the worked example confirms it: after seeding A = [3,1,4,1,5,9] and applying range_update(2, 4, 5), the array becomes [3,6,9,6,5,9]. The formula gives prefix(4) = 24, prefix(1) = 3, so range_query(2,4) = 24 - 3 = 21, matching $6+9+6=21$ directly — and prefix(6) = 38 matches the total $3+6+9+6+5+9=38$.

class FenwickTree:
    """The standard point-update / prefix-query BIT (same as Section 4)."""
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)

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

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


class RangeUpdateRangeQueryBIT:
    """
    Range-add and range-sum, both O(log n), using two ordinary
    FenwickTree instances (B1 over the difference array, B2 over
    the index-weighted difference array).
    """
    def __init__(self, n):
        self.n = n
        self.b1 = FenwickTree(n)  # tracks D
        self.b2 = FenwickTree(n)  # tracks D[j] * (j - 1)

    def _add(self, i, delta):
        if i > self.n:
            return
        self.b1.update(i, delta)
        self.b2.update(i, delta * (i - 1))

    def range_update(self, l, r, delta):
        """Add delta to every position in [l, r] (1-indexed, inclusive)."""
        self._add(l, delta)
        self._add(r + 1, -delta)

    def _prefix_sum(self, i):
        if i <= 0:
            return 0
        return i * self.b1.query(i) - self.b2.query(i)

    def range_query(self, l, r):
        """Sum of positions [l, r] (1-indexed, inclusive)."""
        return self._prefix_sum(r) - self._prefix_sum(l - 1)

    def build(self, values):
        for i in range(1, self.n + 1):
            self.range_update(i, i, values[i - 1])


rrq = RangeUpdateRangeQueryBIT(6)
rrq.build([3, 1, 4, 1, 5, 9])
rrq.range_update(2, 4, 5)
print(rrq.range_query(2, 4))  # 21  (6 + 9 + 6)
print(rrq.range_query(1, 6))  # 38  (3+6+9+6+5+9)

// Range-update / range-query BIT: two FenwickTree instances (dual BIT)
#include <iostream>
#include <vector>
using namespace std;

class FenwickTree {  // same as Section 4
    vector<long long> tree;
    int n;
public:
    FenwickTree(int n) : n(n), tree(n + 1, 0) {}

    void update(int i, long long delta) {
        for (; i <= n; i += i & (-i))
            tree[i] += delta;
    }

    long long query(int i) {
        long long s = 0;
        for (; i > 0; i -= i & (-i))
            s += tree[i];
        return s;
    }
};

class RangeUpdateRangeQueryBIT {
    FenwickTree b1, b2;  // b1 tracks D, b2 tracks D[j] * (j - 1)
    int n;

    void add(int i, long long delta) {
        if (i > n) return;
        b1.update(i, delta);
        b2.update(i, delta * (i - 1));
    }

public:
    RangeUpdateRangeQueryBIT(int n) : b1(n), b2(n), n(n) {}

    void rangeUpdate(int l, int r, long long delta) {
        add(l, delta);
        add(r + 1, -delta);
    }

    long long prefixSum(int i) {
        if (i <= 0) return 0;
        return (long long)i * b1.query(i) - b2.query(i);
    }

    long long rangeQuery(int l, int r) {
        return prefixSum(r) - prefixSum(l - 1);
    }

    void build(const vector<long long>& values) {
        for (int i = 1; i <= n; i++)
            rangeUpdate(i, i, values[i - 1]);
    }
};

int main() {
    RangeUpdateRangeQueryBIT rrq(6);
    rrq.build({3, 1, 4, 1, 5, 9});
    rrq.rangeUpdate(2, 4, 5);
    cout << rrq.rangeQuery(2, 4) << endl;  // 21
    cout << rrq.rangeQuery(1, 6) << endl;  // 38
}

// Range-update / range-query BIT: two FenwickTree instances (dual BIT)
class FenwickTree {  // same as Section 4
    long[] tree;
    int n;

    FenwickTree(int n) {
        this.n = n;
        tree = new long[n + 1];
    }

    void update(int i, long delta) {
        for (; i <= n; i += i & (-i))
            tree[i] += delta;
    }

    long query(int i) {
        long s = 0;
        for (; i > 0; i -= i & (-i))
            s += tree[i];
        return s;
    }
}

class RangeUpdateRangeQueryBIT {
    FenwickTree b1, b2;  // b1 tracks D, b2 tracks D[j] * (j - 1)
    int n;

    RangeUpdateRangeQueryBIT(int n) {
        this.n = n;
        b1 = new FenwickTree(n);
        b2 = new FenwickTree(n);
    }

    private void add(int i, long delta) {
        if (i > n) return;
        b1.update(i, delta);
        b2.update(i, delta * (i - 1));
    }

    void rangeUpdate(int l, int r, long delta) {
        add(l, delta);
        add(r + 1, -delta);
    }

    long prefixSum(int i) {
        if (i <= 0) return 0;
        return (long) i * b1.query(i) - b2.query(i);
    }

    long rangeQuery(int l, int r) {
        return prefixSum(r) - prefixSum(l - 1);
    }

    void build(long[] values) {
        for (int i = 1; i <= n; i++)
            rangeUpdate(i, i, values[i - 1]);
    }
}

public class RangeUpdateRangeQueryDemo {
    public static void main(String[] args) {
        RangeUpdateRangeQueryBIT rrq = new RangeUpdateRangeQueryBIT(6);
        rrq.build(new long[]{3, 1, 4, 1, 5, 9});
        rrq.rangeUpdate(2, 4, 5);
        System.out.println(rrq.rangeQuery(2, 4));  // 21
        System.out.println(rrq.rangeQuery(1, 6));  // 38
    }
}

6. 2D BIT (Binary Indexed Tree over a Matrix)

                Core insight: A 2D BIT is a Fenwick Tree of Fenwick Trees. Instead of a 1D array tree[i], keep a 2D array tree[i][j], and traverse both dimensions with the same i & (-i) trick: an update walks up in rows and, for each row touched, walks up in columns; a query walks down in rows and, for each row, walks down in columns. Rectangle sums come from inclusion-exclusion over four prefix-rectangle queries, exactly like 2D prefix sums.
            

class Fenwick2D:
    """
    Point-update, rectangle-prefix-query BIT over a rows x cols grid.
    Both dimensions are 1-indexed. O(log rows * log cols) per operation.
    """
    def __init__(self, rows, cols):
        self.rows = rows
        self.cols = cols
        self.tree = [[0] * (cols + 1) for _ in range(rows + 1)]

    def update(self, r, c, delta):
        """Add delta to cell (r, c), 1-indexed."""
        i = r
        while i <= self.rows:
            j = c
            while j <= self.cols:
                self.tree[i][j] += delta
                j += j & (-j)
            i += i & (-i)

    def _prefix_query(self, r, c):
        """Sum of the rectangle (1,1) to (r,c) inclusive."""
        s = 0
        i = r
        while i > 0:
            j = c
            while j > 0:
                s += self.tree[i][j]
                j -= j & (-j)
            i -= i & (-i)
        return s

    def range_query(self, r1, c1, r2, c2):
        """Sum of the rectangle (r1,c1) to (r2,c2) inclusive, via
        inclusion-exclusion over four prefix rectangles."""
        return (self._prefix_query(r2, c2)
                - self._prefix_query(r1 - 1, c2)
                - self._prefix_query(r2, c1 - 1)
                + self._prefix_query(r1 - 1, c1 - 1))


# 3x3 grid, all zero, then three point updates
grid = Fenwick2D(3, 3)
grid.update(1, 1, 3)
grid.update(2, 3, 7)
grid.update(3, 2, 4)
print(grid.range_query(1, 1, 2, 3))  # 10  (row1: 3, row2: 7)
print(grid.range_query(2, 1, 3, 3))  # 11  (row2: 7, row3: 4)
print(grid.range_query(1, 1, 3, 3))  # 14  (whole grid: 3+7+4)

// 2D Fenwick Tree: point update, rectangle prefix-sum query
#include <iostream>
#include <vector>
using namespace std;

class Fenwick2D {
    vector<vector<long long>> tree;
    int rows, cols;

    long long prefixQuery(int r, int c) {
        long long s = 0;
        for (int i = r; i > 0; i -= i & (-i))
            for (int j = c; j > 0; j -= j & (-j))
                s += tree[i][j];
        return s;
    }

public:
    Fenwick2D(int rows, int cols) : rows(rows), cols(cols),
        tree(rows + 1, vector<long long>(cols + 1, 0)) {}

    void update(int r, int c, long long delta) {
        for (int i = r; i <= rows; i += i & (-i))
            for (int j = c; j <= cols; j += j & (-j))
                tree[i][j] += delta;
    }

    long long rangeQuery(int r1, int c1, int r2, int c2) {
        return prefixQuery(r2, c2) - prefixQuery(r1 - 1, c2)
             - prefixQuery(r2, c1 - 1) + prefixQuery(r1 - 1, c1 - 1);
    }
};

int main() {
    Fenwick2D grid(3, 3);
    grid.update(1, 1, 3);
    grid.update(2, 3, 7);
    grid.update(3, 2, 4);
    cout << grid.rangeQuery(1, 1, 2, 3) << endl;  // 10
    cout << grid.rangeQuery(2, 1, 3, 3) << endl;  // 11
    cout << grid.rangeQuery(1, 1, 3, 3) << endl;  // 14
}

// 2D Fenwick Tree: point update, rectangle prefix-sum query
public class Fenwick2D {
    long[][] tree;
    int rows, cols;

    Fenwick2D(int rows, int cols) {
        this.rows = rows;
        this.cols = cols;
        tree = new long[rows + 1][cols + 1];
    }

    void update(int r, int c, long delta) {
        for (int i = r; i <= rows; i += i & (-i))
            for (int j = c; j <= cols; j += j & (-j))
                tree[i][j] += delta;
    }

    private long prefixQuery(int r, int c) {
        long s = 0;
        for (int i = r; i > 0; i -= i & (-i))
            for (int j = c; j > 0; j -= j & (-j))
                s += tree[i][j];
        return s;
    }

    long rangeQuery(int r1, int c1, int r2, int c2) {
        return prefixQuery(r2, c2) - prefixQuery(r1 - 1, c2)
             - prefixQuery(r2, c1 - 1) + prefixQuery(r1 - 1, c1 - 1);
    }

    public static void main(String[] args) {
        Fenwick2D grid = new Fenwick2D(3, 3);
        grid.update(1, 1, 3);
        grid.update(2, 3, 7);
        grid.update(3, 2, 4);
        System.out.println(grid.rangeQuery(1, 1, 2, 3));  // 10
        System.out.println(grid.rangeQuery(2, 1, 3, 3));  // 11
        System.out.println(grid.rangeQuery(1, 1, 3, 3));  // 14
    }
}

Trace of the same three updates and the grid they produce (row, col are 1-indexed; blank cells are 0):

	col 1	col 2	col 3
row 1	3
row 2			7
row 3		4

Query	Rectangle	Cells included	Result
`range_query(1,1,2,3)`	rows 1-2, cols 1-3	(1,1)=3, (2,3)=7	10
`range_query(2,1,3,3)`	rows 2-3, cols 1-3	(2,3)=7, (3,2)=4	11
`range_query(1,1,3,3)`	whole grid	(1,1)=3, (2,3)=7, (3,2)=4	14

7. Complexity Analysis

Range-update / point-query: each range update is 2 point updates, each point query is 1 prefix query — $O(\log n)$ per operation, $O(n)$ space.

Range-update / range-query: each range update touches 2 positions on each of 2 BITs (4 point updates total), each range query does 2 prefix-sum evaluations, each of which reads both BITs — still $O(\log n)$ per operation, $O(n)$ space (two arrays of size $n$).

2D BIT over an $n \times m$ grid: a point update or a prefix query walks $O(\log n)$ row steps, and for every row step walks $O(\log m)$ column steps, giving $O(\log n \cdot \log m)$ per operation; a rectangle query is 4 such prefix queries, still $O(\log n \cdot \log m)$. Space is $O(nm)$ for the underlying grid.

8. Applications & Alternatives

Where each variant shows up

Range-update/point-query: bulk score or inventory adjustments where only individual lookups are read back, such as leaderboard bonuses or batched stock adjustments.
Range-update/range-query: time-series or sales dashboards that apply repeated range adjustments (promotions, corrections) and then need arbitrary range totals, such as LeetCode-style "range add, range sum" problems.
2D BIT: mutable spreadsheets, image integral-sum queries after pixel edits, and LeetCode 308 (Range Sum Query 2D - Mutable), where cells are updated one at a time and rectangular sums must stay fast.

A Segment Tree with lazy propagation can also support range-update/range-query, and it generalizes further to non-invertible operations such as range minimum or maximum, where the "subtract to undo" trick behind the dual-BIT formula does not apply. That flexibility costs more code: a recursive tree, a lazy tag, and a push-down step, versus two flat arrays and an XOR-free bit trick here. See the Segment Tree Variants guide for that approach. For sum-like, invertible operations specifically, the BIT variants in this lesson are simpler to write, easier to prove correct by direct algebra, and faster in practice due to better cache locality and lower constant factors.

9. Exercises & Mastery

Easy

Using RangeUpdatePointQueryBIT, build the array [0, 0, 0, 0, 0], apply range_update(1, 3, 4) and range_update(2, 5, 1), then compute point_query(i) for every $i$ by hand before checking against code.
Explain why range_update(i, i, delta) is a valid way to seed or edit a single element, in terms of the two edits it makes to $D$.

Medium

Using RangeUpdateRangeQueryBIT, apply two overlapping range updates to a length-8 array and compute three overlapping range-sum queries by hand, then verify against the direct array.
Derive what changes in the dual-BIT formula if the array is treated as 0-indexed instead of 1-indexed, and confirm your version against the same numeric example used in Section 5.

Hard

Implement LeetCode 308 (Range Sum Query 2D - Mutable) using Fenwick2D, supporting both update(row, col, val) (set, not add — so track the previous value and apply the delta) and sumRegion(r1, c1, r2, c2).
Extend Fenwick2D to support range-update/range-query in two dimensions by generalizing the single-dimension dual-BIT trick; you will need four 2D BITs, not two.

Mastery challenge: A live dashboard receives millions of "add delta to rows $[r_1,r_2]$, columns $[c_1,c_2]$" updates and must answer rectangular-sum queries in real time. Decide which variant applies (hint: it's the answer to exercise 2 in Hard), justify the choice, and state the exact per-operation complexity.

Review rhythm: tomorrow, re-derive the dual-BIT formula from scratch without looking; next week, implement all three variants (range-update/point-query, range-update/range-query, 2D BIT) from memory in one language; several weeks later, recognize which variant a new problem needs before reaching for a Segment Tree by default.

10. Summary Cheat Sheet

Range-update/point-query: run one ordinary Fenwick Tree over the array's difference array $D$; range update is 2 point updates, point query is 1 prefix query.
Range-update/range-query: run two Fenwick Trees, $B_1$ over $D$ and $B_2$ over $D[j]\,(j-1)$; prefix sum is $i \cdot B_1.\text{query}(i) - B_2.\text{query}(i)$.
2D BIT: nest the $i \,\&\, (-i)$ traversal in both dimensions; a point update or prefix query costs $O(\log n \cdot \log m)$, a rectangle query is 4 prefix queries via inclusion-exclusion.
All three variants reuse the same underlying FenwickTree mechanism — nothing new is derived, only recombined.
Segment Tree with lazy propagation is the more general (but heavier) alternative when the operation isn't invertible, such as range min/max.

Cookie Consent

Fenwick Tree Variants: Range Updates, Range Queries & 2D BIT

Table of Contents

1. Introduction & Motivation

2. Prerequisites

3. A Concrete Example

Add 5 to a range, then read individual positions

4. Core Insight: Range-Update / Point-Query via Difference Array

5. Core Insight: Range-Update / Range-Query via Dual BIT

Deriving the formula

6. 2D BIT (Binary Indexed Tree over a Matrix)

7. Complexity Analysis

8. Applications & Alternatives

Where each variant shows up

9. Exercises & Mastery

Easy

Medium

Hard

10. Summary Cheat Sheet

Cookie Consent

Fenwick Tree Variants: Range Updates, Range Queries & 2D BIT

Table of Contents

1. Introduction & Motivation

2. Prerequisites

3. A Concrete Example

Add 5 to a range, then read individual positions

4. Core Insight: Range-Update / Point-Query via Difference Array

5. Core Insight: Range-Update / Range-Query via Dual BIT

Deriving the formula

6. 2D BIT (Binary Indexed Tree over a Matrix)

7. Complexity Analysis

8. Applications & Alternatives

Where each variant shows up

9. Exercises & Mastery

Easy

Medium

Hard

10. Summary Cheat Sheet

Continue the DSA Curriculum

Data Structures & Algorithms Hub

Union-Find, Trie, Fenwick & Segment Tree Guide

Segment Tree Variants