304. 二维区域和检索 - 矩阵不可变

题目

image-20240913170846585

解法

很容易就能看出来这道题是二维的前缀和，但是之前缺少类似的经验，再加上情况比较特殊，直接看的标准答案。

主要核心是使用+1来表示当前点位上从0 0 到i j位置区间内的和

image-20240913171504894

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class NumMatrix {
    vector<vector<int>> sum;
public:
    NumMatrix(vector<vector<int>>& matrix) {
        int m = matrix.size(),n = matrix[0].size();
        sum.resize(m+1,vector<int>(n+1));

        for(int i =0;i<m ;i++)
        {
            for(int j = 0;j<n;j++)
            {
                //这段最后是加上在sum没有被统计进去的小点。
                sum[i+1][j+1] = sum[i+1][j] + sum[i][j+1] - sum[i][j] + matrix[i][j]; 
            }
        }
    }
    
    int sumRegion(int row1, int col1, int row2, int col2) {
        return sum[row2+1][col2+1] - sum[row2+1][col1] - sum[row1][col2+1] + sum[row1][col1];
    }
};