304. Range Sum Query 2D - Immutable

O(mn) time constructor O(1) time call O(mn) space

class NumMatrix {
public:
    NumMatrix(vector<vector<int>> matrix) {
        if (matrix.empty() || matrix[0].empty()) return;
        int n = matrix.size(), m = matrix[0].size();
        mtx.resize(n + 1, vector<int>(m + 1));
        for (int r = 1; r <= n; ++r) {
            for (int c = 1; c <= m; ++c) {
                mtx[r][c] = matrix[r - 1][c - 1] + mtx[r - 1][c] + mtx[r][c - 1] - mtx[r - 1][c - 1];
            }
        }
    }

    int sumRegion(int row1, int col1, int row2, int col2) {
        return mtx[row2 + 1][col2 + 1] - mtx[row1][col2 + 1] - mtx[row2 + 1][col1] + mtx[row1][col1];
    }

    vector<vector<int>> mtx;
};

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix obj = new NumMatrix(matrix);
 * int param_1 = obj.sumRegion(row1,col1,row2,col2);
 */