2D Fenwick Tree for Rectangle Sum Queries
Problem statement
You are given an $n \times n$ matrix $A$ of integers, initially all zeros. You need to support two operations efficiently:
- Point update: Given indices $(i, j)$ and a value $\delta$, set $A[i][j] \leftarrow A[i][j] + \delta$.
- 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.