LeetCode 304 Range Sum Query 2D - Immutable - Example and Complexity Analysis

Consider a $3 \times 3$ matrix: [[1, 2, 3], [4, 5, 6], [7, 8, 9]]

Build prefix sums (with padding row/col of zeros): [[0, 0, 0, 0], [0, 1, 3, 6], [0, 5, 12, 21], [0, 12, 27, 45]]

Query sumRegion(1, 1, 2, 2) (the bottom-right $2 \times 2$): sum = prefix[3][3] - prefix[1][3] - prefix[3][1] + prefix[1][1] sum = 45 - 6 - 12 + 1 = 28

Check: 5 + 6 + 8 + 9 = 28. Correct.

Building prefix matrix: $O(m \times n)$ time and space.

Each query: $O(1)$ time (just 4 lookups and arithmetic).