Leetcode 304 Solution

This article provides solution to leetcode question 304 (range-sum-query-2d-immutable)
Categories:
Tags:
Access this page by simply typing in "lcs 304" in your browser address bar if you have bunnylol configured.

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