DSA-034 · Padded summed-area snapshot and inclusion-exclusion
Range Sum Query 2D — Immutable
Intermediate · Java 21 · Version 1 · editorial draft
Java reference and baseline verified on JDK 21: 20244 deterministic checks. Learner drafts are not executed.
Understand the problem
Build an immutable sum-query object for a rectangular integer matrix, then answer half-open rectangle-sum queries.
- Construct Solution.NumMatrix from a non-null rectangular int[][] with 0–300 rows and 0–300 columns, signed int values, and non-null rows. Both constructors throw IllegalArgumentException for ragged or null rows. A zero-row matrix is treated as 0×0; a positive row count with zero columns is supported.
- sumRegion(r1,c1,r2,c2) returns the long sum over r1≤r<r2 and c1≤c<c2. Require 0≤r1≤r2≤rows and 0≤c1≤c2≤cols; invalid boundaries throw IndexOutOfBoundsException. Empty rectangles return zero, including boundary-only requests.
- Construction preserves the source and captures a snapshot. Later writes to cells or replacement of source rows must not change answers. Stored sums are private. Shared input row objects are allowed because construction only reads them; concurrent source changes during construction are outside the contract.
Examples
Input:
matrix=[[1,2,3],[4,5,6]]; sumRegion(0,1,2,3)
Output:16Rows 0 and 1, columns 1 and 2 contribute 2+3+5+6.
Input:
matrix=[[1,-2],[3,4]]; sumRegion(1,0,2,2)
Output:7The half-open second-row rectangle contains 3 and 4.
Before you start
- Array positions versus prefix boundaries and half-open intervals
- Long arithmetic, frequency maps, and invariant reasoning
Recognize the structure
Many rectangle queries overlap in two dimensions. Store sums from the top-left boundary to every other boundary, then use four values to remove the strips above and left while restoring their doubly-subtracted overlap.
Try before revealing
Hint 1
What does the sum at boundary (r,c) include?
Hint 2
Two removed strips overlap; how often was that overlap subtracted?
Hint 3
Use a padded table and big-above-left+overlap for both construction and queries.
Derive the solution
Reveal the baseline, optimized reasoning, and Java code
Deep-copy and scan each rectangle
Clone every source row so the baseline also preserves snapshot semantics. For [[1,2],[3,4]], query [0,2)×[1,2) scans 2 and 4 for six; querying the whole matrix rescans four cells for ten. Construction takes O(RC+R) time/storage, while a query scans its requested area. A shallow outer-array clone would still share mutable cells.
Improve the baseline
Pad with zero boundaries
Allocate (R+1)×(C+1) long entries. prefix[r][c] sums rows [0,r) and columns [0,c). The first row and column are empty-area sums of zero.
Build by inclusion-exclusion
To compute prefix[r+1][c+1], add the current cell, the rectangle above, and the rectangle left, then subtract their shared upper-left rectangle once.
Extract a query rectangle
Start with prefix[r2][c2], subtract the strip above r1 and the strip left of c1, then add prefix[r1][c1] to restore the overlap removed twice. Keep the same half-open coordinates throughout.
Why it is correct
Construction invariant
In row-major order the required above, left, and upper-left prefixes are already built. Their union plus the current cell is exactly [0,r+1)×[0,c+1), and subtracting the intersection removes its double count. Zero padding proves the boundary base cases.
Query cancellation
An interior query cell appears once in the large prefix and in neither removed strip. A cell in exactly one removed strip cancels. An upper-left overlap cell has coefficient 1-1-1+1=0. Only the requested rectangle remains.
Snapshot, emptiness, and bounds
Computed private sums do not reference source rows, so later mutations cannot affect them. If either pair of boundaries is equal, the four terms cancel to zero. Validated coordinates are valid padded-table indices; zero dimensions and empty loops follow the same formulas.
Complete Java reference and baseline
Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.
public final class Solution {
private static int columns(int[][] matrix) {
int cols = matrix.length == 0 ? 0 : matrix[0] == null ? -1 : matrix[0].length;
for (int[] row : matrix) if (row == null || row.length != cols) throw new IllegalArgumentException("rectangular non-null rows required");
return cols;
}
private static void bounds(int r1, int c1, int r2, int c2, int rows, int cols) {
if (r1 < 0 || r2 < r1 || r2 > rows || c1 < 0 || c2 < c1 || c2 > cols)
throw new IndexOutOfBoundsException("half-open rectangle outside matrix");
}
public static final class NumMatrix {
private final long[][] prefix;
private final int rows, cols;
public NumMatrix(int[][] matrix) {
rows = matrix.length; cols = columns(matrix);
prefix = new long[rows + 1][cols + 1];
for (int r = 0; r < rows; r++) for (int c = 0; c < cols; c++)
prefix[r + 1][c + 1] = (long) matrix[r][c] + prefix[r][c + 1] + prefix[r + 1][c] - prefix[r][c];
}
public long sumRegion(int r1, int c1, int r2, int c2) {
bounds(r1, c1, r2, c2, rows, cols);
return prefix[r2][c2] - prefix[r1][c2] - prefix[r2][c1] + prefix[r1][c1];
}
}
public static final class Baseline {
private final int[][] snapshot;
private final int rows, cols;
public Baseline(int[][] matrix) {
rows = matrix.length; cols = columns(matrix);
snapshot = new int[rows][];
for (int r = 0; r < rows; r++) snapshot[r] = matrix[r].clone();
}
public long sumRegion(int r1, int c1, int r2, int c2) {
bounds(r1, c1, r2, c2, rows, cols);
long sum = 0;
for (int r = r1; r < r2; r++) for (int c = c1; c < c2; c++) sum += snapshot[r][c];
return sum;
}
}
}
Read the meaningful blocks
Cast the cell before arithmetic
A long addend and long prefix entries ensure no int intermediate overflow. At most 90000 int cells contribute, so even inclusion-exclusion intermediates remain safely within long.
Validate shape before building
The helper checks every row once. Assuming matrix[0].length applies to ragged rows would otherwise produce inconsistent storage or incidental exceptions.
Restore the intersection
The fourth positive term is essential; subtracting two strips without it undercounts cells in their overlap.
Complexity
Preprocessing time and persistent storage are O((R+1)(C+1)), including shape validation and padded rows/columns. For positive dimensions this is O(RC); the padded form also describes zero-row or zero-column inputs accurately. Query time and extra query workspace are O(1).
The deep-copy baseline builds in O(RC+R) time/storage and scans O(height·width) cells per nonempty query; loop overhead may additionally visit empty-width rows. Both return one long, not a copied rectangle.
Exact-state walkthroughs
Reveal normal and boundary traces
Build a padded table and query interior and empty areas
Input: {"matrix":[[1,2,3],[4,-5,6],[7,8,9]],"queries":[[1,1,3,3],[0,0,3,3],[1,2,1,3]]} · Query answers: [18,35,0]
Step 1 of 14: Validate the rectangle and initialize zero boundary strips.
The first row and column sum empty areas. Null slots display not-yet-built cells; queries wait until construction finishes.
Dots mark unbuilt cells. Each completed entry at (r,c) sums source rows [0,r) and columns [0,c).
Empty at this step.
| Variable | Value |
|---|---|
| sourceMatrix | [[1,2,3],[4,-5,6],[7,8,9]] |
| prefixTable | [[0,0,0,0],[0,null,null,null],[0,null,null,null],[0,null,null,null]] |
| answers | [] |
See the affected Java block
1 public final class Solution { 2 private static int columns(int[][] matrix) { 3 int cols = matrix.length == 0 ? 0 : matrix[0] == null ? -1 : matrix[0].length; 4 for (int[] row : matrix) if (row == null || row.length != cols) throw new IllegalArgumentException("rectangular non-null rows required"); 5 return cols; 6 } 7 private static void bounds(int r1, int c1, int r2, int c2, int rows, int cols) { 8 if (r1 < 0 || r2 < r1 || r2 > rows || c1 < 0 || c2 < c1 || c2 > cols) 9 throw new IndexOutOfBoundsException("half-open rectangle outside matrix"); 10 } 11 public static final class NumMatrix { 12 private final long[][] prefix; 13 private final int rows, cols; 14 public NumMatrix(int[][] matrix) { 15 rows = matrix.length; cols = columns(matrix); 16 prefix = new long[rows + 1][cols + 1]; 17 for (int r = 0; r < rows; r++) for (int c = 0; c < cols; c++) 18 prefix[r + 1][c + 1] = (long) matrix[r][c] + prefix[r][c + 1] + prefix[r + 1][c] - prefix[r][c]; 19 } 20 public long sumRegion(int r1, int c1, int r2, int c2) { 21 bounds(r1, c1, r2, c2, rows, cols); 22 return prefix[r2][c2] - prefix[r1][c2] - prefix[r2][c1] + prefix[r1][c1]; 23 } 24 } 25 public static final class Baseline { 26 private final int[][] snapshot; 27 private final int rows, cols; 28 public Baseline(int[][] matrix) { 29 rows = matrix.length; cols = columns(matrix); 30 snapshot = new int[rows][]; 31 for (int r = 0; r < rows; r++) snapshot[r] = matrix[r].clone(); 32 } 33 public long sumRegion(int r1, int c1, int r2, int c2) { 34 bounds(r1, c1, r2, c2, rows, cols); 35 long sum = 0; 36 for (int r = r1; r < r2; r++) for (int c = c1; c < c2; c++) sum += snapshot[r][c]; 37 return sum; 38 } 39 } 40 } 41
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Validate the rectangle and initialize zero boundary strips.
The first row and column sum empty areas. Null slots display not-yet-built cells; queries wait until construction finishes.
- sourceMatrix
[[1,2,3],[4,-5,6],[7,8,9]]- prefixTable
[[0,0,0,0],[0,null,null,null],[0,null,null,null],[0,null,null,null]]- answers
[]
- Build one upper-left area from completed neighbors.
The above and left rectangles overlap once; subtracting their intersection restores one count per cell.
- sourceMatrix
[[1,2,3],[4,-5,6],[7,8,9]]- prefixTable
[[0,0,0,0],[0,1,null,null],[0,null,null,null],[0,null,null,null]]- r
0- c
0- answers
[]
- Build one upper-left area from completed neighbors.
The above and left rectangles overlap once; subtracting their intersection restores one count per cell.
- sourceMatrix
[[1,2,3],[4,-5,6],[7,8,9]]- prefixTable
[[0,0,0,0],[0,1,3,null],[0,null,null,null],[0,null,null,null]]- r
0- c
1- answers
[]
- Build one upper-left area from completed neighbors.
The above and left rectangles overlap once; subtracting their intersection restores one count per cell.
- sourceMatrix
[[1,2,3],[4,-5,6],[7,8,9]]- prefixTable
[[0,0,0,0],[0,1,3,6],[0,null,null,null],[0,null,null,null]]- r
0- c
2- answers
[]
- Build one upper-left area from completed neighbors.
The above and left rectangles overlap once; subtracting their intersection restores one count per cell.
- sourceMatrix
[[1,2,3],[4,-5,6],[7,8,9]]- prefixTable
[[0,0,0,0],[0,1,3,6],[0,5,null,null],[0,null,null,null]]- r
1- c
0- answers
[]
- Build one upper-left area from completed neighbors.
The above and left rectangles overlap once; subtracting their intersection restores one count per cell.
- sourceMatrix
[[1,2,3],[4,-5,6],[7,8,9]]- prefixTable
[[0,0,0,0],[0,1,3,6],[0,5,2,null],[0,null,null,null]]- r
1- c
1- answers
[]
- Build one upper-left area from completed neighbors.
The above and left rectangles overlap once; subtracting their intersection restores one count per cell.
- sourceMatrix
[[1,2,3],[4,-5,6],[7,8,9]]- prefixTable
[[0,0,0,0],[0,1,3,6],[0,5,2,11],[0,null,null,null]]- r
1- c
2- answers
[]
- Build one upper-left area from completed neighbors.
The above and left rectangles overlap once; subtracting their intersection restores one count per cell.
- sourceMatrix
[[1,2,3],[4,-5,6],[7,8,9]]- prefixTable
[[0,0,0,0],[0,1,3,6],[0,5,2,11],[0,12,null,null]]- r
2- c
0- answers
[]
- Build one upper-left area from completed neighbors.
The above and left rectangles overlap once; subtracting their intersection restores one count per cell.
- sourceMatrix
[[1,2,3],[4,-5,6],[7,8,9]]- prefixTable
[[0,0,0,0],[0,1,3,6],[0,5,2,11],[0,12,17,null]]- r
2- c
1- answers
[]
- Build one upper-left area from completed neighbors.
The above and left rectangles overlap once; subtracting their intersection restores one count per cell.
- sourceMatrix
[[1,2,3],[4,-5,6],[7,8,9]]- prefixTable
[[0,0,0,0],[0,1,3,6],[0,5,2,11],[0,12,17,35]]- r
2- c
2- answers
[]
- Extract the requested half-open rectangle with four terms.
big-above-left+overlap leaves exactly the queried area, including zero when either dimension is empty.
- sourceMatrix
[[1,2,3],[4,-5,6],[7,8,9]]- prefixTable
[[0,0,0,0],[0,1,3,6],[0,5,2,11],[0,12,17,35]]- r1
1- c1
1- r2
3- c2
3- big
35- above
6- leftStrip
12- overlap
1- answer
18- answers
[18]
- Extract the requested half-open rectangle with four terms.
big-above-left+overlap leaves exactly the queried area, including zero when either dimension is empty.
- sourceMatrix
[[1,2,3],[4,-5,6],[7,8,9]]- prefixTable
[[0,0,0,0],[0,1,3,6],[0,5,2,11],[0,12,17,35]]- r1
0- c1
0- r2
3- c2
3- big
35- above
0- leftStrip
0- overlap
0- answer
35- answers
[18,35]
- Extract the requested half-open rectangle with four terms.
big-above-left+overlap leaves exactly the queried area, including zero when either dimension is empty.
- sourceMatrix
[[1,2,3],[4,-5,6],[7,8,9]]- prefixTable
[[0,0,0,0],[0,1,3,6],[0,5,2,11],[0,12,17,35]]- r1
1- c1
2- r2
1- c2
3- big
6- above
6- leftStrip
3- overlap
3- answer
0- answers
[18,35,0]
- Complete the query sequence; each query returns one long.
The result follows the declared boundaries, multiplicities, strictness, and numeric contract.
- result
[18,35,0]
Zero columns still allow boundary queries
Input: {"matrix":[[],[]],"queries":[[0,0,2,0],[2,0,2,0]]} · Query answers: [0,0]
Step 1 of 4: Validate the rectangle and initialize zero boundary strips.
The first row and column sum empty areas. Null slots display not-yet-built cells; queries wait until construction finishes.
Dots mark unbuilt cells. Each completed entry at (r,c) sums source rows [0,r) and columns [0,c).
Empty at this step.
| Variable | Value |
|---|---|
| sourceMatrix | [[],[]] |
| prefixTable | [[0],[0],[0]] |
| answers | [] |
See the affected Java block
1 public final class Solution { 2 private static int columns(int[][] matrix) { 3 int cols = matrix.length == 0 ? 0 : matrix[0] == null ? -1 : matrix[0].length; 4 for (int[] row : matrix) if (row == null || row.length != cols) throw new IllegalArgumentException("rectangular non-null rows required"); 5 return cols; 6 } 7 private static void bounds(int r1, int c1, int r2, int c2, int rows, int cols) { 8 if (r1 < 0 || r2 < r1 || r2 > rows || c1 < 0 || c2 < c1 || c2 > cols) 9 throw new IndexOutOfBoundsException("half-open rectangle outside matrix"); 10 } 11 public static final class NumMatrix { 12 private final long[][] prefix; 13 private final int rows, cols; 14 public NumMatrix(int[][] matrix) { 15 rows = matrix.length; cols = columns(matrix); 16 prefix = new long[rows + 1][cols + 1]; 17 for (int r = 0; r < rows; r++) for (int c = 0; c < cols; c++) 18 prefix[r + 1][c + 1] = (long) matrix[r][c] + prefix[r][c + 1] + prefix[r + 1][c] - prefix[r][c]; 19 } 20 public long sumRegion(int r1, int c1, int r2, int c2) { 21 bounds(r1, c1, r2, c2, rows, cols); 22 return prefix[r2][c2] - prefix[r1][c2] - prefix[r2][c1] + prefix[r1][c1]; 23 } 24 } 25 public static final class Baseline { 26 private final int[][] snapshot; 27 private final int rows, cols; 28 public Baseline(int[][] matrix) { 29 rows = matrix.length; cols = columns(matrix); 30 snapshot = new int[rows][]; 31 for (int r = 0; r < rows; r++) snapshot[r] = matrix[r].clone(); 32 } 33 public long sumRegion(int r1, int c1, int r2, int c2) { 34 bounds(r1, c1, r2, c2, rows, cols); 35 long sum = 0; 36 for (int r = r1; r < r2; r++) for (int c = c1; c < c2; c++) sum += snapshot[r][c]; 37 return sum; 38 } 39 } 40 } 41
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Validate the rectangle and initialize zero boundary strips.
The first row and column sum empty areas. Null slots display not-yet-built cells; queries wait until construction finishes.
- sourceMatrix
[[],[]]- prefixTable
[[0],[0],[0]]- answers
[]
- Extract the requested half-open rectangle with four terms.
big-above-left+overlap leaves exactly the queried area, including zero when either dimension is empty.
- sourceMatrix
[[],[]]- prefixTable
[[0],[0],[0]]- r1
0- c1
0- r2
2- c2
0- big
0- above
0- leftStrip
0- overlap
0- answer
0- answers
[0]
- Extract the requested half-open rectangle with four terms.
big-above-left+overlap leaves exactly the queried area, including zero when either dimension is empty.
- sourceMatrix
[[],[]]- prefixTable
[[0],[0],[0]]- r1
2- c1
0- r2
2- c2
0- big
0- above
0- leftStrip
0- overlap
0- answer
0- answers
[0,0]
- Complete the query sequence; each query returns one long.
The result follows the declared boundaries, multiplicities, strictness, and numeric contract.
- result
[0,0]
Test the contract
Input:
matrix=[]; sumRegion(0,0,0,0)
Output:0The 0×0 snapshot still has a padded origin.
Input:
matrix=[[],[]]; sumRegion(0,0,2,0)
Output:0A zero-column rectangle is empty.
Input:
matrix=[[2147483647,2147483647]]; sumRegion(0,0,1,2)
Output:4294967294Wide rectangle sum.
Input:
matrix=[[1],[2,3]]
Output:IllegalArgumentExceptionRagged input is rejected at construction.
Common mistakes and counterexamples
Forget the overlap restoration
Counterexample: For [[1,2],[3,4]], the single cell [1,2)×[1,2) must be four, not three.
Use big-above-left+overlap.
Deep-copy only the outer array in the baseline
Counterexample: Changing source[0][0] would change a shared row’s query results.
Clone each row or store a fully independent summed-area table.
Mix inclusive cell indices with boundary coordinates
Counterexample: On a 2×2 matrix, r2=2 is a valid end boundary but not a readable source-row index.
Validate and pass half-open boundaries consistently; convert an inclusive external API once.
Follow-ups
Support mutable point updates.
An ordinary summed-area snapshot needs many entries repaired after a write. A 2D Fenwick tree supports logarithmic updates and rectangle queries with different storage and API contracts.
Use inclusive rectangle coordinates.
Convert bottom-right (r2,c2) to exclusive (r2+1,c2+1) once after validating source indices. Do not use +1 on coordinates that are already boundaries.
Handle sparse huge coordinate domains.
A dense (R+1)(C+1) table may be impossible. Consider coordinate compression, offline sweep-line queries, or a sparse indexed structure based on the update/query workload; do not claim dense preprocessing stays cheap.
Your Java attempt
Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.
Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.
No unsaved text changes · 275/20,000 characters
Self-review
Use the checklist to test your explanation. Checks apply to this visit.