2D Fenwick Tree for Rectangle Sum Queries

Reported in interviews at Bank of America Barclays Citadel Two Sigma

Problem statement

You are given an $n \times n$ matrix $A$ of integers, initially all zeros. You need to support two operations efficiently:

  1. Point update: Given indices $(i, j)$ and a value $\delta$, set $A[i][j] \leftarrow A[i][j] + \delta$.
  2. Rectangle sum query: Given corners $(x_1, y_1)$ and $(x_2, y_2)$ with $1 \le x_1 \le x_2 \le n$ and $1 \le y_1 \le y_2 \le n$, return

$$S(x_1, y_1, x_2, y_2) = \sum_{i=x_1}^{x_2} \sum_{j=y_1}^{y_2} A[i][j].$$

Design a 2D Binary Indexed Tree (Fenwick Tree) that achieves $O(\log^2 n)$ per update and per query, using $O(n^2)$ space.

Constraints

  • $1 \le n \le 1024$
  • Coordinates are 1-indexed
  • Values and sums fit in a 64-bit signed integer
  • Up to $10^5$ operations (updates and queries mixed)

Requirements

(i) Give the complete data structure and index arithmetic for both update(x, y, delta) and query(x1, y1, x2, y2).

(ii) Handle edge cases: empty rectangles (where $x_1 > x_2$ or $y_1 > y_2$), single-cell queries, and boundary indices.

(iii) Provide a working implementation.

Example 1

  • Input: $n = 4$. Update $(2, 3, 5)$, Update $(1, 1, 3)$, Query $(1, 1, 2, 3)$.
  • Output: $8$
  • Explanation: After updates, $A[2][3] = 5$ and $A[1][1] = 3$. The rectangle from $(1,1)$ to $(2,3)$ contains both cells, so the sum is $3 + 5 = 8$.

Example 2

  • Input: $n = 3$. Update $(1, 1, 10)$, Update $(3, 3, 20)$, Query $(2, 2, 3, 3)$.
  • Output: $20$
  • Explanation: Only $A[3][3] = 20$ falls inside the query rectangle $(2,2)$ to $(3,3)$.

Function signature: implement run_ops(n, ops) where n is the matrix dimension and ops is a list of operations. Each op is either ["update", x, y, delta] (apply $A[x][y] \mathrel{+}= \delta$, 1-indexed, no output) or ["query", x1, y1, x2, y2] (append the rectangle sum $S(x_1,y_1,x_2,y_2)$ to the result). Return the list of query results in order; empty rectangles ($x_1>x_2$ or $y_1>y_2$) contribute $0$.

Example

run_ops(4, [["update", 2, 3, 5], ["update", 1, 1, 3], ["query", 1, 1, 2, 3]]) -> [8]

After the two updates $A[2][3]=5$ and $A[1][1]=3$; the query rectangle from $(1,1)$ to $(2,3)$ contains both cells, so its sum is $3+5=8$, returned as the single-element list [8].

Show hint

What 1D structure answers prefix sums with point updates in logarithmic time, and what happens if you run it once per coordinate?

Relevant roles: ML Engineer, AI Engineer, Forward Deployed Engineer and LLM Engineer.

Related free problems