C++二维前缀和

二维前缀和输入一个 n 行 m 列的整数矩阵再输入 q 个询问每个询问包含四个整数 x1 , y1 , x2 , y2 表示一个子矩阵,(x1,y1)为左上角坐标x2,y2为右下角坐标。对于每个询问输出子矩阵中所有数的和。定义两个二维数组一个存矩阵的数字a[][]一个存和s[][],s[i][j]表示在二维数组中左上角1,1到右下角i,j所包围的矩阵元素的和。二维前缀和预处理公式s[i][j]s[i-1][j]s[i][j-1]-s[i-1][j-1]a[i][j]二位前缀和结论sums[x2][y2]-s[x1-1][y2]-s[x2][y1-1]s[x1-1][y1-1]#includebits/stdc.h using namespace std; int main(){ int n,m,q; cinnmq; int a[n1][m1];//存矩阵的元素 int s[n1][m1];//存矩阵范围内元素和 for(int i1;in;i){//循环从1开始 for(int j1;jm;j){ cina[i][j]; } } for(int i1;in;i){ for(int j1;jm;j){ s[i][j]s[i-1][j]s[i][j-1]a[i][j]-s[i-1][j-1];//二维前缀和预处理公式 } } int x1,y1,x2,y2; while(q--){ int sum0; cinx1y1x2y2; sums[x2][y2]-s[x1-1][y2]-s[x2][y1-1]s[x1-1][y1-1];//二位前缀和结论 coutsumendl; } return 0; }