算法笔记：Day-04（二维前缀和）

二维数组及滚动数组

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

class NumMatrix {
   private final int[][] sum;

   public NumMatrix(int[][] matrix) {
       int m = matrix.length;
       int n = matrix[0].length;
       sum = new int[m + 1][n + 1];
       for (int i = 0; i < m; i++) {
           for (int j = 0; j < n; j++) {
               sum[i + 1][j + 1] = sum[i + 1][j] + sum[i][j + 1] - sum[i][j] + matrix[i][j];
           }
       }
   }

   // 返回左上角在 (r1,c1) 右下角在 (r2,c2) 的子矩阵元素和
   public int sumRegion(int r1, int c1, int r2, int c2) {
       return sum[r2 + 1][c2 + 1] - sum[r2 + 1][c1] - sum[r1][c2 + 1] + sum[r1][c1];
   }
}

作者：灵茶山艾府
链接：https://leetcode.cn/problems/range-sum-query-2d-immutable/solutions/2667331/tu-jie-yi-zhang-tu-miao-dong-er-wei-qian-84qp/

这道题真的很好，板子题

标签：前缀,04,min,int,res,sum,List,Day,Math
From： https://blog.csdn.net/2302_78571314/article/details/143258078