力扣（LeetCode）308. 二维区域和检索 - 可变（2022.11.05）

给你一个二维矩阵 matrix ，你需要处理下面两种类型的若干次查询：

更新：更新 matrix 中某个单元的值。
求和：计算矩阵 matrix 中某一矩形区域元素的 和 ，该区域由 左上角 (row1, col1) 和 右下角 (row2, col2) 界定。
实现 NumMatrix 类：

NumMatrix(int[][] matrix) 用整数矩阵 matrix 初始化对象。
void update(int row, int col, int val) 更新 matrix[row][col] 的值到 val 。
int sumRegion(int row1, int col1, int row2, int col2) 返回矩阵 matrix 中指定矩形区域元素的 和 ，该区域由 左上角 (row1, col1) 和 右下角 (row2, col2) 界定。

示例 1：
输入

[“NumMatrix”, “sumRegion”, “update”, “sumRegion”]
[[[[3, 0, 1, 4, 2], [5, 6, 3, 2, 1], [1, 2, 0, 1, 5], [4, 1, 0, 1, 7], [1, 0, 3, 0, 5]]], [2, 1, 4, 3], [3, 2, 2], [2, 1, 4, 3]]
输出
[null, 8, null, 10]

解释

NumMatrix numMatrix = new NumMatrix([[3, 0, 1, 4, 2], [5, 6, 3, 2, 1], [1, 2, 0, 1, 5], [4, 1, 0, 1, 7], [1, 0, 3, 0, 5]]);
numMatrix.sumRegion(2, 1, 4, 3); // 返回 8 (即, 左侧红色矩形的和)
numMatrix.update(3, 2, 2); // 矩阵从左图变为右图
numMatrix.sumRegion(2, 1, 4, 3); // 返回 10 (即，右侧红色矩形的和)

提示：

m == matrix.length
n == matrix[i].length
1 <= m, n <= 200
-10⁵ <= matrix[i][j] <= 10⁵
0 <= row < m
0 <= col < n
-10⁵ <= val <= 10⁵
0 <= row1 <= row2 < m
0 <= col1 <= col2 < n
最多调用10⁴ 次 sumRegion 和 update 方法

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/range-sum-query-2d-mutable

方法一：二维前缀和

C++提交内容：

class NumMatrix {
public:
    NumMatrix(vector<vector<int>>& matrix) {
        this->matrix = matrix;
        if (matrix.empty() || matrix[0].empty()) {
            return;
        }

        rowCount = matrix.size();
        colCount = matrix[0].size();
        rowSumArr = vector<vector<int>>(rowCount, vector<int>(colCount, 0));
        for (int i = 0; i < rowCount; i++) {
            rowSumArr[i][0] = matrix[i][0];
            for (int j = 1; j < colCount; j++) {
                rowSumArr[i][j] = rowSumArr[i][j - 1] + matrix[i][j];
            }
        }
    } 
    
    void update(int row, int col, int val) {
        matrix[row][col] = val;
        int fromCol = col;
        if (col == 0) {
            rowSumArr[row][col] = matrix[row][col];
            fromCol = col + 1;
        }

        for (int j = fromCol; j < colCount; j++) {
            rowSumArr[row][j] = rowSumArr[row][j - 1] + matrix[row][j];
        }
    }
    
    int sumRegion(int row1, int col1, int row2, int col2) {
        int sum = 0;
        for (int i = row1; i <= row2; i++) {
            sum += col1 == 0 ? rowSumArr[i][col2] : rowSumArr[i][col2] - rowSumArr[i][col1 - 1];
        }

        return sum;
    }

private:
    vector<vector<int>> matrix;
    vector<vector<int>> rowSumArr;
    int rowCount;
    int colCount;
};

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix* obj = new NumMatrix(matrix);
 * obj->update(row,col,val);
 * int param_2 = obj->sumRegion(row1,col1,row2,col2);
 */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54