plaintext function NumMatrix(matrix) m := rows of matrix n := cols of matrix pref := 2D array of size (m + 1) x (n + 1), filled with 0 // Build 2D prefix sums for i from 1 to m for j from 1 to n pref[i][j] := matrix[i-1][j-1] + pref[i-1][j] + pref[i][j-1] - pref[i-1][j-1] function sumRegion(r1, c1, r2, c2) // Convert to 1-indexed r1++ c1++ r2++ c2++ return pref[r2][c2] - pref[r1-1][c2] - pref[r2][c1-1] + pref[r1-1][c1-1]
Time: O(mn) to build, O(1) per query. Space: O(mn).
The formula adds the top-left rectangle twice (once in each subtraction), so you add it back once. Visualizing the four rectangles makes this clear.