利用DP、容斥原理的思想。
s [ i ] [ j ] s[i][j] s[i][j] 记录从 [ 1 ] [ 1 ] [1][1] [1][1]到 [ i ] [ j ] [i][j] [i][j]形成的矩形的区域和。状态更新： s [ i ] [ j ] = s [ i − 1 ] [ j ] + s [ i ] [ j − 1 ] − s [ i − 1 ] [ j − 1 + g [ i ] [ j ] s[i][j] =s[i-1][j]+s[i][j-1]-s[i-1][j-1+g[i][j] s[i][j]=s[i−1][j]+s[i][j−1]−s[i−1][j−1+g[i][j] 下标从1开始求 [ x 1 ] [ y 1 ] [x1][y1] [x1][y1]到 [ x 2 ] [ y 2 ] [x2][y2] [x2][y2]形成的矩形的区域和: a r e a = s [ x 2 ] [ y 2 ] − s [ x 1 − 1 ] [ y 2 ] − s [ x 2 ] [ y 1 − 1 ] + s [ x 1 − 1 ] [ y 1 − 1 ] area = s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1] area=s[x2][y2]−s[x1−1][y2]−s[x2][y1−1]+s[x1−1][y1−1] class NumMatrix { vector<vector<int>> s; int m = 0 , n = 0; public: NumMatrix(vector<vector<int>>& g) { m = g.size()a if(m) n = g[0].size(); if(n==0) return; s.resize(m+1,vector<int>(n+1,0)); for(int i=1;i<=m;i++){ for(int j=1;j<=n;j++){ s[i][j] = s[i-1][j]+s[i][j-1]-s[i-1][j-1]+g[i-1][j-1]; } } } int sumRegion(int x1, int y1, int x2, int y2) { if(n==0) return 0; x1++, y1++, x2++, y2++; // 下标从1开始 return s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]; } }; /** * Your NumMatrix object will be instantiated and called as such: * NumMatrix* obj = new NumMatrix(matrix); * int param_1 = obj->sumRegion(row1,col1,row2,col2); */模板题：304. 二维区域和检索 - 矩阵不可变
