Consider a 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 ):
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: time and space.
Each query: time (just 4 lookups and arithmetic).