2D Fenwick Tree: Matrix Prefix Sums

Key Insights

• 2D Fenwick Trees extend the “tree of trees” concept to support O(log n × log m) point updates and rectangle sum queries on mutable matrices
• The inclusion-exclusion principle transforms any rectangle query into four prefix sum queries, making the implementation surprisingly elegant
• Choose 2D Fenwick Trees over prefix sum arrays when updates are frequent, and over 2D segment trees when you only need sum queries (not min/max)

The Problem with Matrix Range Queries

You have a matrix of integers. You need to answer thousands of queries asking for the sum of elements within arbitrary rectangles. Oh, and the matrix values change between queries.

The naive approach—iterating through every cell in the rectangle—gives you O(n × m) per query. With a 1000×1000 matrix and 10,000 queries, you’re looking at 10 billion operations. That’s not going to fly.

Static prefix sum arrays solve the query problem in O(1), but they crumble the moment you need to update a single cell—rebuilding costs O(n × m). 2D segment trees handle both operations in O(log n × log m), but they’re complex to implement and use 4× the memory.

The 2D Fenwick Tree (or 2D Binary Indexed Tree) hits the sweet spot: O(log n × log m) for both updates and queries, with minimal implementation complexity and reasonable memory overhead.

This data structure shows up constantly in competitive programming, but it’s equally valuable in production systems handling heat maps, cumulative analytics dashboards, and game development scenarios where you need regional statistics on dynamic grids.

1D Fenwick Tree Refresher

Before jumping to two dimensions, let’s nail down the 1D version. A Fenwick Tree stores partial sums in a clever way that allows both point updates and prefix sum queries in O(log n).

The magic lies in the lowbit operation: x & (-x) extracts the lowest set bit of x. This determines how many elements each position “covers” and drives the index traversal.

class FenwickTree1D:
    def __init__(self, n: int):
        self.n = n
        self.tree = [0] * (n + 1)  # 1-indexed
    
    def update(self, i: int, delta: int) -> None:
        """Add delta to position i."""
        while i <= self.n:
            self.tree[i] += delta
            i += i & (-i)  # Move to parent
    
    def prefix_sum(self, i: int) -> int:
        """Return sum of elements [1, i]."""
        total = 0
        while i > 0:
            total += self.tree[i]
            i -= i & (-i)  # Move to previous range
        return total
    
    def range_sum(self, left: int, right: int) -> int:
        """Return sum of elements [left, right]."""
        return self.prefix_sum(right) - self.prefix_sum(left - 1)

The update operation climbs “up” the implicit tree by repeatedly adding the lowbit. The query operation walks “down” by subtracting the lowbit, accumulating partial sums along the way.

Extending to Two Dimensions

The conceptual leap to 2D is straightforward: instead of storing integers at each position, store an entire 1D Fenwick Tree. When you update position (x, y), you update the y-position in multiple 1D trees (those covering x). When you query, you accumulate from multiple 1D trees.

Think of it as a Fenwick Tree where each node contains another Fenwick Tree. The outer tree handles rows; the inner trees handle columns.

The space complexity is O(n × m)—you’re storing a flattened 2D array, just with a different interpretation of what each cell means.

class FenwickTree2D:
    def __init__(self, rows: int, cols: int):
        self.rows = rows
        self.cols = cols
        # 1-indexed, so we need (rows+1) x (cols+1)
        self.tree = [[0] * (cols + 1) for _ in range(rows + 1)]
    
    def update(self, row: int, col: int, delta: int) -> None:
        """Add delta to position (row, col)."""
        i = row
        while i <= self.rows:
            j = col
            while j <= self.cols:
                self.tree[i][j] += delta
                j += j & (-j)
            i += i & (-i)
    
    def prefix_sum(self, row: int, col: int) -> int:
        """Return sum of rectangle from (1,1) to (row, col)."""
        total = 0
        i = row
        while i > 0:
            j = col
            while j > 0:
                total += self.tree[i][j]
                j -= j & (-j)
            i -= i & (-i)
        return total

Notice the nested loops. For update, we iterate through all positions that “cover” our target in the row dimension, and for each of those, we iterate through all covering positions in the column dimension. The query works symmetrically but in reverse.

Rectangle Sum Queries

The prefix sum gives us the sum from (1, 1) to (row, col). But real applications need arbitrary rectangles: sum from (r1, c1) to (r2, c2).

This is where inclusion-exclusion saves us. Visualize it:

    1       c1-1    c1      c2
  1 +--------+-------+-------+
    |   A    |   B   |       |
r1-1+--------+-------+       |
    |   C    |   D   |       |
  r1+--------+-------+-------+
    |        |       |       |
  r2+--------+-------+-------+

The sum of rectangle D (from r1,c1 to r2,c2) equals:

• prefix_sum(r2, c2) — everything
• minus prefix_sum(r1-1, c2) — removes A+B
• minus prefix_sum(r2, c1-1) — removes A+C
• plus prefix_sum(r1-1, c1-1) — adds back A (subtracted twice)

def range_sum(self, r1: int, c1: int, r2: int, c2: int) -> int:
    """Return sum of rectangle from (r1, c1) to (r2, c2) inclusive."""
    return (self.prefix_sum(r2, c2)
            - self.prefix_sum(r1 - 1, c2)
            - self.prefix_sum(r2, c1 - 1)
            + self.prefix_sum(r1 - 1, c1 - 1))

Four prefix queries, each O(log n × log m), giving us O(log n × log m) for any rectangle sum.

Complete Implementation with Initialization

Here’s a production-ready implementation that handles initialization from an existing matrix:

class FenwickTree2D:
    def __init__(self, matrix: list[list[int]] = None, rows: int = 0, cols: int = 0):
        if matrix:
            self.rows = len(matrix)
            self.cols = len(matrix[0]) if matrix else 0
        else:
            self.rows = rows
            self.cols = cols
        
        self.tree = [[0] * (self.cols + 1) for _ in range(self.rows + 1)]
        self.original = [[0] * (self.cols + 1) for _ in range(self.rows + 1)]
        
        if matrix:
            for i in range(self.rows):
                for j in range(self.cols):
                    self.set(i + 1, j + 1, matrix[i][j])
    
    def update(self, row: int, col: int, delta: int) -> None:
        i = row
        while i <= self.rows:
            j = col
            while j <= self.cols:
                self.tree[i][j] += delta
                j += j & (-j)
            i += i & (-i)
    
    def set(self, row: int, col: int, value: int) -> None:
        """Set position (row, col) to value."""
        delta = value - self.original[row][col]
        self.original[row][col] = value
        self.update(row, col, delta)
    
    def prefix_sum(self, row: int, col: int) -> int:
        if row <= 0 or col <= 0:
            return 0
        total = 0
        i = row
        while i > 0:
            j = col
            while j > 0:
                total += self.tree[i][j]
                j -= j & (-j)
            i -= i & (-i)
        return total
    
    def range_sum(self, r1: int, c1: int, r2: int, c2: int) -> int:
        return (self.prefix_sum(r2, c2)
                - self.prefix_sum(r1 - 1, c2)
                - self.prefix_sum(r2, c1 - 1)
                + self.prefix_sum(r1 - 1, c1 - 1))

The set method tracks original values to compute deltas—essential when you need to set absolute values rather than add deltas.

Complexity Analysis and Trade-offs

Choose 2D prefix sums when your matrix is static. The O(1) query is unbeatable.

Choose 2D Fenwick Trees when you need updates and only care about sum queries. The implementation is clean and memory-efficient.

Choose 2D segment trees when you need range min/max queries or more complex operations that don’t support the Fenwick Tree’s implicit structure.

Practical Application: LeetCode 308

Let’s solve “Range Sum Query 2D - Mutable” to see this in action:

class NumMatrix:
    def __init__(self, matrix: list[list[int]]):
        if not matrix or not matrix[0]:
            self.bit = None
            return
        
        rows, cols = len(matrix), len(matrix[0])
        self.bit = FenwickTree2D(matrix)
    
    def update(self, row: int, col: int, val: int) -> None:
        # Convert to 1-indexed
        self.bit.set(row + 1, col + 1, val)
    
    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        # Convert to 1-indexed
        return self.bit.range_sum(row1 + 1, col1 + 1, row2 + 1, col2 + 1)

This passes all test cases with comfortable margins on time limits.

Beyond competitive programming, 2D Fenwick Trees excel at:

• Heat map analytics: Track cumulative user interactions in screen regions
• Game development: Compute fog-of-war visibility or resource counts in map sectors
• Image processing: Running sums for box blur operations on dynamic images
• Sparse matrices: When most cells are zero, the log factors dominate the theoretical nm space

The 2D Fenwick Tree isn’t the flashiest data structure, but it’s a reliable workhorse. When you need mutable matrix range sums, it’s almost always the right choice.