1
/**
2
 * @param {number[][]} matrix
3
 */
4
var NumMatrix = function (matrix) {
5
  const n = matrix.length,
6
    m = matrix[0].length;
7
  // n * m filled with 0
8
  this.prefix = Array.from({ length: n }, (_, i) => {
9
    return new Array(m).fill(0);
10
  });
11
  const prefix = this.prefix;
12
  // precompute
13
  for (let i = 0; i < m; i++) {
14
    if (i == 0) prefix[0][i] = matrix[0][i];
15
    else prefix[0][i] = prefix[0][i - 1] + matrix[0][i];
16
  }
17
  for (let i = 0; i < n; i++) {
18
    if (i == 0) continue;
19
    else prefix[i][0] = prefix[i - 1][0] + matrix[i][0];
20
  }
21

22
  for (let i = 1; i < n; i++) {
23
    for (let j = 1; j < m; j++) {
24
      prefix[i][j] =
25
        prefix[i - 1][j] +
26
        prefix[i][j - 1] -
27
        prefix[i - 1][j - 1] +
28
        matrix[i][j];
29
    }
30
  }
31
};
32

33
/**
34
 * @param {number} row1
35
 * @param {number} col1
36
 * @param {number} row2
37
 * @param {number} col2
38
 * @return {number}
39
 */
40
NumMatrix.prototype.sumRegion = function (row1, col1, row2, col2) {
41
  const prefix = this.prefix;
42
  const biggerRectSum = prefix[row2][col2];
43
  if (row1 == col1 && row1 == 0) return biggerRectSum;
44
  if (row1 == 0 || col1 == 0) {
45
    let subtractRegion = 0;
46
    if (row1 == 0) subtractRegion = prefix[row2][col1 - 1];
47
    else subtractRegion = prefix[row1 - 1][col2];
48
    return biggerRectSum - subtractRegion;
49
  }
50
  return (
51
    biggerRectSum -
52
    prefix[row1 - 1][col2] -
53
    prefix[row2][col1 - 1] +
54
    prefix[row1 - 1][col1 - 1]
55
  );
56
};
57

58
/**
59
 * Your NumMatrix object will be instantiated and called as such:
60
 * var obj = new NumMatrix(matrix)
61
 * var param_1 = obj.sumRegion(row1,col1,row2,col2)
62
 */