Leetcode 304 Solution

This article provides solution to leetcode question 304 (range-sum-query-2d-immutable)

https://leetcode.com/problems/range-sum-query-2d-immutable

Solution

class NumMatrix { vector<vector<int>> a; public: NumMatrix(vector<vector<int>> &matrix) { int m = matrix.size(); if (m == 0) return;
int n = matrix[0].size();
for (int i = 0; i < m; i++) a.push_back(vector<int>(n));
a[0][0] = matrix[0][0];
for (int i = 1; i < m; i++) a[i][0] = a[i - 1][0] + matrix[i][0];
for (int j = 1; j < n; j++) a[0][j] = a[0][j - 1] + matrix[0][j];
for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { a[i][j] = a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1] + matrix[i][j]; } } }
int sumRegion(int row1, int col1, int row2, int col2) { int area1 = 0; int area2 = 0; int area3 = 0;
if (row1 != 0 && col1 != 0) area1 = a[row1 - 1][col1 - 1];
if (row1 != 0) area2 = a[row1 - 1][col2];
if (col1 != 0) area3 = a[row2][col1 - 1];
return a[row2][col2] - area2 - area3 + area1; } };
// Your NumMatrix object will be instantiated and called as such: // NumMatrix numMatrix(matrix); // numMatrix.sumRegion(0, 1, 2, 3); // numMatrix.sumRegion(1, 2, 3, 4);