算法分析
画出一个完整的方格,将其图形化,有利于理解
主要分为两个部分:
-
预处理前缀和,
s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j]
-
推导前缀和公式,
S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]
模板
S[i, j] = 第i行j列格子左上部分所有元素的和
S[i, j] = S[i-1, j] + S[i, j-1] - s[i-1, j-1] + a[i, j]
以(x1, y1)为左上角,(x2, y2)为右下角的子矩阵的和为:
S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]
AC代码
#include<iostream>
using namespace std;
int n, m, q;
const int N = 1e3+5;
int a[N][N], s[N][N];
int main()
{
cin>>n>>m>>q;
for(int i=1;i<=n;i++)
for (int j = 1; j<=m; j++){
cin>>a[i][j];
s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j];
}
while(q--)
{
int x1, y1, x2, y2;
cin>>x1>>y1>>x2>>y2;
cout<< s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1] <<endl;
}
return 0;
}