LeetCode - 304. Range Sum Query 2D - Immutable

Thoughts:

I choose prefix sum and dynamic programming to solve this problem. Prefix sum is for storing every size of the rectangle’s sum in O(n), but can get the range by O(1). Dynamical programming is for dividing the rectangle into four parts and calculating the sum of each part in O(1).

Thoughts visuzlization:

matrix: [
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9]
]

dp: [
  [1, 3, 6],
  [5, 12, 21],
  [12, 27, 45]
]

Every element in dp is the sum of the rectangle from matrix[0][0] to matrix[i][j].

dp[1][1] (the sum of rectangle of size 2x2, 1 + 2 + 4 + 5) =
matrix[1][1] (the new element, 12) +
dp[0][1] (the sum of the top rectangle, 1 + 2) +
dp[1][0] (the sum of the left rectangle, 1 + 4) -
dp[0][0] (the sum of the top-left rectangle, 1, the duplicated one)

so the pattern is dp[i][j] = matrix[i][j] + dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]

but I need to replace the boundary of dp with 0, so the dp will be like dp[i][j] = matrix[i][j] + (dp[i-1]?.[j] ?? 0) + (dp[i][j-1] ?? 0) - (dp[i-1]?.[j-1] ?? 0)

if I want to get the sum of the rectangle from matrix[row1][col1] to matrix[row2][col2]

and set the row1 is 1, col1 is 1, row2 is 2, col2 is 2

dp[2][2] (the sum of rectangle of size 3x3) -
dp[0][2] (the sum of the top rectangle) -
dp[2][0] (the sum of the left rectangle) +
dp[0][0] (the sum of the top-left rectangle, the duplicated one)

so the pattern is dp[row2+1][col2+1] - dp[row1-1][col2] - dp[row2][col1-1] + dp[row1-1][col1-1]

but I need to replace the boundary of dp with 0, so the dp will be like dp[row2+1][col2+1] - (dp[row1-1]?.[col2] ?? 0) - dp[row2][col1-1] + (dp[row1-1]?.[col1-1] ?? 0)

Code:

/**
 * @param {number[][]} matrix
 */
var NumMatrix = function (matrix) {
  const m = matrix.length;
  const n = matrix[0].length;
  this.dp = new Array(m).fill(0).map(() => new Array(n).fill(0));
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      this.dp[i][j] =
        matrix[i][j] +
        (this.dp[i - 1]?.[j] ?? 0) +
        (this.dp[i][j - 1] ?? 0) -
        (this.dp[i - 1]?.[j - 1] ?? 0);
    }
  }
};

/**
 * @param {number} row1
 * @param {number} col1
 * @param {number} row2
 * @param {number} col2
 * @return {number}
 */
NumMatrix.prototype.sumRegion = function (row1, col1, row2, col2) {
  return (
    this.dp[row2][col2] -
    (this.dp[row1 - 1]?.[col2] ?? 0) -
    (this.dp[row2][col1 - 1] ?? 0) +
    (this.dp[row1 - 1]?.[col1 - 1] ?? 0)
  );
};

Reference

Original link

Basic prefix sum

Dynamic programming 師大