参考资料来源灵神在力扣所发的题单，仅供分享学习笔记和记录，无商业用途。
核心思路：本质上是求矩阵元素和，以(0,0)开始，到(当前下标)结束的矩阵元素和
前缀和公式：ans[i+1][j+1]=ans[i+1][j]+ans[i][j+1]-ans[i][j]+matrix[i][j];
区间和计算公式：ans[row2+1][col2+1]-ans[row2+1][col1]-ans[row1][col2+1]+ans[row1][col1];
应用场景：快速求二维区间内元素和问题
class NumMatrix {
public:
vector<vector<int>> ans;
NumMatrix(vector<vector<int>>& matrix) {
int m=matrix.size(),n=matrix[0].size();
ans.resize(m+1,vector<int>(n+1));
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
ans[i+1][j+1]=ans[i+1][j]+ans[i][j+1]-ans[i][j]+matrix[i][j];
}
}
}
//求(row1,col1)到(row2,col2)矩阵范围内的元素和
int sumRegion(int row1, int col1, int row2, int col2) {
return ans[row2+1][col2+1]-ans[row2+1][col1]-ans[row1][col2+1]+ans[row1][col1];
}
};
/**
* Your NumMatrix object will be instantiated and called as such:
* NumMatrix* obj = new NumMatrix(matrix);
* int param_1 = obj->sumRegion(row1,col1,row2,col2);
*/题意：给定一个二维数据和一个k，按照要求计算出矩阵元素和。
思路：根据条件可以计算出矩阵开头和结尾位置，采用二维前缀和计算即可
class Solution {
public:
vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
//题意：给定一个二维数据和一个k，按照要求计算出矩阵元素和。
//思路：根据条件可以计算出矩阵开头和结尾位置，采用二维前缀和计算即可
int m=mat.size(),n=mat[0].size();
vector<vector<int>> ans(m+1,vector<int>(n+1));
vector<vector<int>> ret(m,vector<int>(n));
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
ans[i+1][j+1]=ans[i+1][j]+ans[i][j+1]-ans[i][j]+mat[i][j];
}
}
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
int r1=max(0,i-k);
int r2=min(m-1,i+k);
int c1=max(0,j-k);
int c2=min(n-1,j+k);
ret[i][j]=ans[r2+1][c2+1]-ans[r2+1][c1]-ans[r1][c2+1]+ans[r1][c1];
}
}
return ret;
}
};题意：计算出以当前位置作为结束点的矩阵元素异或，求第k大目标值
思路：异或原理(a^a^a)=a,所以ans[i+1][j]^ans[i][j+1]相交部分为0，^ans[i][j]后补全相交部分，最后^matrix[i][j]即可
class Solution {
public:
int kthLargestValue(vector<vector<int>>& matrix, int k) {
//题意：计算出以当前位置作为结束点的矩阵元素异或，求第k大目标值
//思路：异或原理(a^a^a)=a,所以ans[i+1][j]^ans[i][j+1]相交部分为0，^ans[i][j]后补全相交部分，最后^matrix[i][j]即可
int m=matrix.size(),n=matrix[0].size();
vector<vector<int>> ans(m+1,vector<int>(n+1));
vector<int> ret;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
//加法中 “重复部分” 需要用减法抵消（+a -a = 0）；
//异或中 “重复部分” 需要用再异或一次抵消（a ^ a ^ a = a，通过自反性恢复）。
ans[i+1][j+1]=ans[i+1][j]^ans[i][j+1]^ans[i][j]^matrix[i][j];
ret.push_back(ans[i+1][j+1]);
}
}
sort(ret.begin(),ret.end());
return ret[ret.size()-k];
}
};思路：分别统计当前位置所构成的矩阵中有多少个x和y，当x大于0并且x==y的时候统计数量
class Solution {
public:
int numberOfSubmatrices(vector<vector<char>>& grid) {
//思路：分别统计当前位置所构成的矩阵中有多少个x和y，当x大于0并且x==y的时候统计数量
int m=grid.size(),n=grid[0].size();
int ret=0;
vector<vector<int>> x(m+1,vector<int>(n+1)),y(m+1,vector<int>(n+1));
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
x[i+1][j+1]=x[i+1][j]+x[i][j+1]-x[i][j]+(grid[i][j]=='X');
y[i+1][j+1]=y[i+1][j]+y[i][j+1]-y[i][j]+(grid[i][j]=='Y');
if(x[i+1][j+1]!=0 && x[i+1][j+1]==y[i+1][j+1]) ret++;
}
}
return ret;
}
};题意：给定一个矩阵，求矩阵为正方形并且元素和小于等于threshold的正方形的最大边长
思路：在当前位置行和列中选取最小的那个作为可减数，既保证了不超过地址范围的最大可操作数，又能保证矩阵减去后为正方形
二维前缀和矩阵区间求解：大矩形减去终点行，起点列-1，再减去起点行-1，终点列，再加回被多减的重叠部分(起点行-1，起点列-1)。
class Solution {
public:
int maxSideLength(vector<vector<int>>& mat, int threshold) {
//题意：给定一个矩阵，求矩阵为正方形并且元素和小于等于threshold的正方形的最大边长
//思路：在当前位置行和列中选取最小的那个作为可减数，既保证了不超过地址范围的最大可操作数，又能保证矩阵减去后为正方形
//二维前缀和矩阵区间求解：大矩形减去终点行，起点列-1，再减去起点行-1，终点列，再加回被多减的重叠部分(起点行-1，起点列-1)。
int m=mat.size(),n=mat[0].size(),ret=0;
vector<vector<int>> ans(m+1,vector<int>(n+1));
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
ans[i+1][j+1]=ans[i+1][j]+ans[i][j+1]-ans[i][j]+mat[i][j];
}
}
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
int c=min(i,j);
for(int k=c;k>=1;k--){
int buff=ans[i][j]-ans[i-k][j]-ans[i][j-k]+ans[i-k][j-k];
if(buff<=threshold){
ret=max(k,ret);
break;
}
}
}
}
return ret;
}
};