【前缀和】LCR_013_二维区域和检索-矩阵不可变

求解代码

privateint[][]preSum;publicNumMatrix(int[][]matrix){intm=matrix.length;intn=matrix[0].length;if(m==0||n==0){return;}preSum=newint[m+1][n+1];for(inti=1;i<=m;i++){for(intj=1;j<=n;j++){preSum[i][j]=preSum[i-1][j]+preSum[i][j-1]+matrix[i-1][j-1]-preSum[i-1][j-1];}}}publicintsumRegion(introw1,intcol1,introw2,intcol2){returnpreSum[row2+1][col2+1]-preSum[row2+1][col1]-preSum[row1][col2+1]+preSum[row1][col1];}

小贴士

预处理：preSum[i][j] = 上 + 左 + 当前元素 - 重复部分；

查询：区域和 = 整体和 - 左侧和 - 上方和 + 重复和。