Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

Two-dimensional Fenwick tree: update cells and sum rectangles

Last updated: 5 Oct 20269 min read
tutorial
IntermediateBy AITrove Editorial

A two-dimensional Fenwick tree extends prefix sums across rows and columns. Each stored cell summarizes a rectangle determined by the lowest set bit of its one-based row and column indexes. Assigning a warehouse quantity first computes its difference from the prior quantity; that difference is added to every Fenwick summary that covers the cell. A prefix query returns the sum in [0, row_stop) by [0, column_stop). A general half-open rectangle uses four prefixes by inclusion and exclusion. Rows and columns are independent dimensions, and a zero-width or zero-height rectangle has sum zero.

Operational case

In a four-row, five-column warehouse, record 47 units at cell (1, 2), 61 at (2, 3), and 19 at (3, 4). Rectangle [1, 3) by [2, 4) contains the first two cells and sums to 108. Reassign (1, 2) to 26, so that same rectangle sums to 87; the whole grid now sums to 106. The coordinate contract is zero-based for public calls and one-based inside the Fenwick loops. Calling assign twice with the same quantity must leave the totals unchanged. Swapping row and column indexes silently corrupts answers on a nonsquare grid.

Working Python program

python
"""Point assignments and half-open rectangular sums on a fixed grid."""


class WarehouseGrid:
    def __init__(self, rows: int, columns: int):
        if rows <= 0 or columns <= 0:
            raise ValueError("grid dimensions must be positive")
        self.rows, self.columns = rows, columns
        self.values = [[0] * columns for _ in range(rows)]
        self.tree = [[0] * (columns + 1) for _ in range(rows + 1)]

    def assign(self, row: int, column: int, quantity: int) -> None:
        if not 0 <= row < self.rows or not 0 <= column < self.columns:
            raise IndexError((row, column))
        difference = quantity - self.values[row][column]
        self.values[row][column] = quantity
        row_index = row + 1
        while row_index <= self.rows:
            column_index = column + 1
            while column_index <= self.columns:
                self.tree[row_index][column_index] += difference
                column_index += column_index & -column_index
            row_index += row_index & -row_index

    def prefix(self, row_stop: int, column_stop: int) -> int:
        if not 0 <= row_stop <= self.rows or not 0 <= column_stop <= self.columns:
            raise IndexError((row_stop, column_stop))
        total = 0
        row_index = row_stop
        while row_index:
            column_index = column_stop
            while column_index:
                total += self.tree[row_index][column_index]
                column_index -= column_index & -column_index
            row_index -= row_index & -row_index
        return total

    def rectangle(self, row_start: int, row_stop: int, column_start: int, column_stop: int) -> int:
        if not 0 <= row_start <= row_stop <= self.rows or not 0 <= column_start <= column_stop <= self.columns:
            raise IndexError((row_start, row_stop, column_start, column_stop))
        return (self.prefix(row_stop, column_stop)
                - self.prefix(row_start, column_stop)
                - self.prefix(row_stop, column_start)
                + self.prefix(row_start, column_start))


warehouse = WarehouseGrid(4, 5)
warehouse.assign(1, 2, 47)
warehouse.assign(2, 3, 61)
warehouse.assign(3, 4, 19)
print(warehouse.rectangle(1, 3, 2, 4))
warehouse.assign(1, 2, 26)
print(warehouse.rectangle(1, 3, 2, 4))
print(warehouse.rectangle(0, 4, 0, 5))

Output

Output
108
87
106

Time, space, and tradeoff

For R rows and C columns, storage is O(RC) integers for both the current grid and Fenwick summaries. Point assignment and prefix sum take O(log R log C) time and O(1) working space. A rectangle query makes four prefix calls and has the same asymptotic bound. Building by repeated assignments costs O(RC log R log C) if every cell is populated; a direct bulk build could improve preprocessing. A sparse warehouse with enormous dimensions and few occupied cells should use coordinate compression or a sparse index instead of this dense allocation. The dimensions remain fixed after construction.

Common Mistakes

  • Do not add a replacement quantity without subtracting the old quantity.
  • Do not omit the final inclusion-exclusion corner term.
  • Do not confuse inclusive cell coordinates with half-open rectangle stops.
  • Do not allocate a dense R by C grid for a huge sparse coordinate space.

Connected lessons

Apply the invariant in the warehouse indexes project, then check the operations quiz.

Two-dimensional prefixes: constant-time static rectangle sums extends this operation choice.

Compressed 2D Fenwick trees: toggle known points and count rectangles adds a distinct structure contract to compare.

Two-dimensional segment trees: correct sensors and sum rectangles adds a related structure with a different operation boundary.

data structures
range-query-structures
Storage details