题目思路
搞清楚重複的地方
公式
- 公式1:S[i][j]=S[i-1][j]+S[i][j-1]-S[i-1][j-1]+A[i][j]
- 公式2: 子矩阵和:S[x2][y2]-S[x2][y1-1]-S[x1-1][y2]+S[x1-1][y1-1]
C++ 核心代码
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>A[i][j];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
B[i][j] =A[i][j]+ B[i-1][j] + B[i][j-1] - B[i-1][j-1]; // A[i-1][j-1]是被加了两次的部分 所以刪掉一個
while(q--){
int x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;
cout<<B[x2][y2] - B[x2][y1-1] - B[x1-1][y2] + B[x1-1][y1-1]<<endl;
}