我一開始還以為在侮辱我的智商, 但真的蠢的是我自己
一開始以為O(n²)傻傻算就好, 其實這可以用交集去解掉
注意邊界問題
class NumMatrix {
public:
NumMatrix(vector<vector<int>>& matrix) {
int m = matrix.size();
int n = matrix[0].size();
sum_mat = vector<vector<int>>(m + 1, vector<int>(n + 1, 0));
for(int i = 1; i <= m;i++){
for(int j = 1; j <= n;j++){
sum_mat[i][j] = matrix[i - 1][j - 1] + sum_mat[i][j - 1] + sum_mat[i - 1][j] - sum_mat[i - 1][j - 1];
}
}
}
int sumRegion(int row1, int col1, int row2, int col2) {return sum_mat[row2 + 1][col2 + 1] - sum_mat[row2+ 1][col1] - sum_mat[row1][col2 + 1] + sum_mat[row1][col1];
}
vector<vector<int>> sum_mat;
};/**
* Your NumMatrix object will be instantiated and called as such:
* NumMatrix* obj = new NumMatrix(matrix);
* int param_1 = obj->sumRegion(row1,col1,row2,col2);
*/
