Dynamic Programming21 sections · 916 units
Open in Course

LeetCode 304 Range Sum Query 2D - Walkthrough

2D prefix sums trace

Build 2D prefix sums for a 3×33 \times 3 matrix. Let prefix[i][j]prefix[i][j] = sum of submatrix from (0,0)(0,0) to (i−1,j−1)(i-1, j-1).

Formula: prefix[i][j]=matrix[i−1][j−1]+prefix[i−1][j]+prefix[i][j−1]−prefix[i−1][j−1]prefix[i][j] = matrix[i-1][j-1] + prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1]. Query (r1,c1,r2,c2)(r1, c1, r2, c2): prefix[r2+1][c2+1]−prefix[r1][c2+1]−prefix[r2+1][c1]+prefix[r1][c1]prefix[r2+1][c2+1] - prefix[r1][c2+1] - prefix[r2+1][c1] + prefix[r1][c1]. The −- and ++ handle inclusion-exclusion: subtract top and left regions, add back the doubly-subtracted corner.