Range Sum Query 2D - Immutable

medium prefix sum matrix design

Problem

Design a data structure that supports repeated rectangular sum queries on an immutable matrix.

Inputmatrix = [[3,0,1,4,2],[5,6,3,2,1]]; sumRegion(0,1,1,3)

Output17

Inclusion-exclusion: p[r2+1][c2+1] − p[r1][c2+1] − p[r2+1][c1] + p[r1][c1].

matrix (rows ';' cells ',')

class NumMatrix:
    def __init__(self, m):
        R, C = len(m), len(m[0]) if m else 0
        self.p = [[0]*(C+1) for _ in range(R+1)]
        for r in range(R):
            for c in range(C):
                self.p[r+1][c+1] = m[r][c] + self.p[r][c+1] + self.p[r+1][c] - self.p[r][c]
    def sumRegion(self, r1, c1, r2, c2):
        return (self.p[r2+1][c2+1] - self.p[r1][c2+1]
              - self.p[r2+1][c1] + self.p[r1][c1])

class NumMatrix {
  constructor(m) {
    const R = m.length, C = m[0].length;
    this.p = Array.from({length: R + 1}, () => new Array(C + 1).fill(0));
    for (let r = 0; r < R; r++)
      for (let c = 0; c < C; c++)
        this.p[r+1][c+1] = m[r][c] + this.p[r][c+1] + this.p[r+1][c] - this.p[r][c];
  }
  sumRegion(r1, c1, r2, c2) {
    return this.p[r2+1][c2+1] - this.p[r1][c2+1] - this.p[r2+1][c1] + this.p[r1][c1];
  }
}

class NumMatrix {
    int[][] p;
    public NumMatrix(int[][] m) {
        int R = m.length, C = m[0].length;
        p = new int[R + 1][C + 1];
        for (int r = 0; r < R; r++)
            for (int c = 0; c < C; c++)
                p[r+1][c+1] = m[r][c] + p[r][c+1] + p[r+1][c] - p[r][c];
    }
    public int sumRegion(int r1, int c1, int r2, int c2) {
        return p[r2+1][c2+1] - p[r1][c2+1] - p[r2+1][c1] + p[r1][c1];
    }
}

class NumMatrix {
    vector> p;
public:
    NumMatrix(vector>& m) {
        int R = m.size(), C = m[0].size();
        p.assign(R + 1, vector(C + 1, 0));
        for (int r = 0; r < R; r++)
            for (int c = 0; c < C; c++)
                p[r+1][c+1] = m[r][c] + p[r][c+1] + p[r+1][c] - p[r][c];
    }
    int sumRegion(int r1, int c1, int r2, int c2) {
        return p[r2+1][c2+1] - p[r1][c2+1] - p[r2+1][c1] + p[r1][c1];
    }
};

Explanation

We want to answer many rectangle-sum queries fast. Adding up the cells inside each rectangle every time is slow, so we precompute a 2D prefix-sum table once and then answer each query in constant time.

The table p is one row and one column bigger than the matrix. We define p[r+1][c+1] as the sum of every cell in the rectangle from the top-left corner down to (r, c). It is built with p[r+1][c+1] = m[r][c] + p[r][c+1] + p[r+1][c] - p[r][c]: add the cell, add the block above and the block to the left, then subtract the overlap that was counted twice.

To answer sumRegion(r1, c1, r2, c2) we use inclusion-exclusion on four corners: p[r2+1][c2+1] - p[r1][c2+1] - p[r2+1][c1] + p[r1][c1]. We take the big block, peel off the strip above and the strip to the left, then add back the top-left corner that got removed twice.

Example: with the corner sums precomputed, asking for a 3-row by 3-column window becomes just those four lookups and three +/− operations — no looping over the cells at all.

Building the table costs O(R·C) once, and every query after that is O(1).

Time: O(RC) build, O(1) query Space: O(RC)