# LeetCode: Range Sum Query 2d Immutable Solution

```.css-ds3kc{display:table-row;}.css-1t8atru{display:table-cell;opacity:0.5;padding-right:var(--chakra-space-6);-webkit-user-select:none;-moz-user-select:none;-ms-user-select:none;user-select:none;text-align:right;}1.css-2qghsv{display:table-cell;}/**2 * Your NumMatrix object will be instantiated and called as such:3 * var obj = new NumMatrix(matrix)4 * var param_1 = obj.sumRegion(row1,col1,row2,col2)5 */6
7// row-based prefix sums8/**9 * @param {number[][]} matrix10 */11var NumMatrix = function (matrix) {12  ;[this.M, this.N] = [matrix.length, matrix[0].length]13
14  this.prefixSum = Array.from({ length: this.M }, _ => Array(this.N).fill())15
16  for (let row = 0; row < this.M; row++) {17    for (let col = 0; col < this.N; col++) {18      this.prefixSum[row][col] =19        matrix[row][col] + (this.prefixSum[row][col - 1] || 0)20    }21  }22}23
24/**25 * @param {number} row126 * @param {number} col127 * @param {number} row228 * @param {number} col229 * @return {number}30 */31NumMatrix.prototype.sumRegion = function (row1, col1, row2, col2) {32  let sum = 033  for (let row = row1; row <= row2; row++) {34    sum += this.prefixSum[row][col2] - (this.prefixSum[row][col1 - 1] || 0)35  }36  return sum37}38
39// sub matrix40/**41 * @param {number[][]} matrix42 */43var NumMatrix = function (matrix) {44  ;[this.M, this.N] = [matrix.length, matrix[0].length]45
46  this.prefixSum = Array.from({ length: this.M + 1 }, _ =>47    Array(this.N + 1).fill(0)48  )49
50  for (let row = 0; row < this.M; row++) {51    for (let col = 0; col < this.N; col++) {52      this.prefixSum[row + 1][col + 1] =53        this.prefixSum[row + 1][col] +54        this.prefixSum[row][col + 1] -55        this.prefixSum[row][col] +56        matrix[row][col]57    }58  }59}60
61/**62 * @param {number} row163 * @param {number} col164 * @param {number} row265 * @param {number} col266 * @return {number}67 */68NumMatrix.prototype.sumRegion = function (row1, col1, row2, col2) {69  return (70    this.prefixSum[row2 + 1][col2 + 1] -71    this.prefixSum[row1][col2 + 1] -72    this.prefixSum[row2 + 1][col1] +73    this.prefixSum[row1][col1]74  )75}```

## Tags

leetcode

array

dynamic programming

## Next Post

LeetCode: Ambiguous Coordinates

May 13, 2021

Search Posts