Prefix Sums on 2D Arrays: Matrix Range Queries

Concepts: py2DPrefixSum, pyInclusionExclusion, pyMatrixQuery

The 1D prefix sum extends naturally to 2D. Instead of prefix[i] storing the sum of a prefix of a row, prefix2d[r][c] stores the sum of the entire rectangular submatrix from (0,0) to (r-1, c-1). Building this takes O(m*n) time and space. Then any rectangular submatrix sum query answers in O(1). This comes up in interviews at companies where data is naturally 2D: grid-based metrics, image processing pipelines, geographic aggregations, or any problem involving 'sum of a rectangular region.' Building the 2D Prefix Sum Matrix The inclusion-exclusion formula is the key to 2D prefix sums. You want the rectangle from (r1,c1) to (r2,c2). prefix[r2+1][c2+1] gives the entire rectangle from (0,0) to (r2,c2). But that includes the top strip (rows 0..r1-1) and the left strip (cols 0..c1-1). You subtract