# Leetcode 304 Solution

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);
``````