· By John Kavanagh

Range Sum Query in Two Dimensions: Subtract Two Strips, Restore the Corner

An aerial view of neighbouring cultivated fields with parallel crop rows.
Image by Kristaps Ungurs, licensed from Unsplash.

The memorable part of a two‑dimensional range sum is the final plus sign. We subtract the rows above a rectangle and the columns to its left, then add the upper‑left corner back because both subtractions removed it.

I prefer understanding that overlap before learning the four‑term formula. Otherwise the formula becomes a small arrangement of indices and signs that is surprisingly easy to copy incorrectly and surprisingly tedious to debug.

The LeetCode Range Sum Query 2D problem asks for repeated rectangle sums over a fixed matrix, with constant‑time queries. The public coordinates include both corner cells. We'll build a padded table of rectangular prefixes so that queries touching the top or left edge use exactly the same expression as interior queries.


Define the Rectangle Behind Each Cell

Let prefix[r][c] be the sum of matrix cells in rows before r and columns before c. Both limits are exclusive. A prefix at [r][c] therefore covers an r‑by‑c rectangle anchored at the matrix's upper‑left corner.

An extra first row and first column contain zeroes. They represent rectangles with no height or no width. The complete table has rows + 1 rows and columns + 1 columns.

This convention means prefix[0][c] and prefix[r][0] are valid, useful values rather than cases we have to avoid. Padding is doing semantic work: empty rectangles are real base cases for the arithmetic.

For a source cell at [r][c], the corresponding new prefix lies at [r + 1][c + 1]. It combines the prefix above, the prefix to the left, and the source cell, then removes their shared upper‑left overlap.

That gives cell + above + left - overlap. The subtraction is needed because the above and left prefixes both contain the same earlier rectangle. The construction and query formulas use the same inclusion‑exclusion idea in opposite directions.


Trace an Interior Rectangle

Consider this matrix:

RowColumn 0Column 1Column 2
0214
13‑25
2061

Its padded prefix table is:

Prefix row0123
00000
10237
205413
3051020

Suppose we query rows one through two and columns one through two. The requested cells are minus two, five, six, and one, with total ten.

Start with prefix[3][3], which covers the whole matrix and totals twenty. Remove the strip above the query using prefix[1][3], which is seven. Remove the strip to its left using prefix[3][1], which is five.

The top‑left cell, worth two, belonged to both removed strips. We've subtracted it twice even though it appeared only once in the starting total. Add prefix[1][1] back, giving 20 - 7 - 5 + 2 = 10.

Negative cells don't change the argument. We're adding and subtracting regions by membership, not relying on their totals being positive or increasing.


The Complete Class

class NumMatrix {
  private readonly prefix: number[][];

  constructor(matrix: number[][]) {
    const rows = matrix.length;
    const columns = matrix[0].length;
    this.prefix = Array.from({ length: rows + 1 }, () =>
      Array<number>(columns + 1).fill(0),
    );

    for (let row = 0; row < rows; row += 1) {
      for (let column = 0; column < columns; column += 1) {
        this.prefix[row + 1][column + 1] =
          matrix[row][column] +
          this.prefix[row][column + 1] +
          this.prefix[row + 1][column] -
          this.prefix[row][column];
      }
    }
  }

  sumRegion = (
    row1: number,
    col1: number,
    row2: number,
    col2: number,
  ): number =>
    this.prefix[row2 + 1][col2 + 1] -
    this.prefix[row1][col2 + 1] -
    this.prefix[row2 + 1][col1] +
    this.prefix[row1][col1];
}

The constructor visits source cells from top to bottom and left to right. At each point, the prefixes above, left, and diagonally above‑left have already been calculated. That order satisfies the dependency graph without recursion.

The query uses four table reads and three arithmetic operations, independent of rectangle size. Construction costs O(rows × columns) time, and the padded table uses O(rows × columns) additional space for a non‑empty matrix. Each query costs O(1).

The matrix is guaranteed to be non‑empty and rectangular, and query coordinates are valid. A general‑purpose wrapper could validate those conditions, but this implementation deliberately follows the judge's interface and promises.


Allocate Distinct Rows

The Array.from callback constructs a new array for every row. That's necessary because a two‑dimensional JavaScript array is an array of references, not a block of independent numeric cells by default.

Filling an outer array with one already‑created inner array would make all rows refer to the same object. Updating one prefix row would then change every apparent row at the same column. The resulting failure can look like an arithmetic problem when the formula is completely innocent.

This is why I would keep a non‑square matrix with varied values in the tests. Symmetrical or all‑zero examples are rather accommodating witnesses and can hide both allocation and indexing mistakes.

The constructor also builds independent storage instead of modifying the caller's matrix. Later changes to that original matrix do not update this object's answers. As with any immutable prefix structure, these are sums of a snapshot taken at construction.


Bounds and Changing Workloads

The problem allows at most 200 rows and 200 columns, with each cell's magnitude at most 10,000. A full‑matrix sum has magnitude at most 400 million. Even intermediate additions and subtractions here remain well within JavaScript's exact integer range.

Those bounds justify number for this implementation. They don't imply that arbitrary spreadsheet totals or high‑precision decimal quantities can use the same numeric type without thought. The rectangle formula and the representation of its values are separate decisions.

If cells change frequently, a cached rectangular prefix table needs substantial repair after each update. A two‑dimensional Fenwick tree or another update‑aware structure may suit that workload better. The fixed‑matrix promise is what makes the simple table attractive here.

For repeated rectangles in an image or grid, this representation is also commonly called a summed‑area table. The useful idea is the same: pay once to summarise all prefixes, then recover a region by cancelling unwanted parts.


Check Every Edge, Then Every Small Rectangle

I would begin with a one‑cell matrix, a single row, a single column, and a rectangular matrix with unequal dimensions. Query a corner cell, the whole matrix, an interior rectangle, and rectangles touching each edge.

For stronger verification, use a direct nested‑loop reference that adds every requested source cell. On small matrices, enumerate every valid pair of row limits and column limits and compare all rectangles. The reference should not use any prefix arithmetic, so an incorrect sign or offset cannot be shared accidentally.

A horizontal or vertical split provides another property: the two non‑overlapping pieces must sum to the original rectangle. Transposing the matrix and swapping row and column coordinates should preserve the result. These checks are useful additions, but exact reference comparisons still do the main work.

My Subarray Sum Equals K walkthrough develops prefix reasoning in one dimension. My Number of Islands article uses the same kind of matrix input for connectivity instead of arithmetic. Sharing a grid representation doesn't make the underlying questions interchangeable.


Keep the Overlap Visible

The four‑term query is easier to recover when we can name its regions: the large prefix, the top strip, the left strip, and their shared corner. Padding supplies empty strips at the edges, so no branch changes that explanation.

That's the version I'd want to find during a later code review. The final plus sign is restoring something specific, and every index points to a clearly defined rectangle.


Untangling a delivery problem?

Send the symptoms, constraints, and affected routes. I'll help identify whether the issue sits in the application, platform, content model, deployment path, or search surface.