二维前缀和

公式：s[i][j]= s[i-1][j] + s[i][j-1] -s[i-1][j-1] + a[i][j];

求子矩阵：s[x2][y2] - s[x2][y1-1] -s[x1-1][y2] +s[x1-1][y1-1];

代码：
/***

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

using namespace std;

int n,m,q;
const int N = 1001;
int a[1001][1001];
int s[1001][1001];

int main()
{
s[0][0]=0;
cin >> n>> m>>q;
for(int i =1;i<=n;i)
{
for(int j=1;j<=m;j)
{
scanf(“%d”,&a[i][j]);
}
}
for(int i =1;i<=n;i)
for(int j=1;j<=m;j)
s[i][j] = s[i-1][j]+s[i][j-1] -s[i-1][j-1]+a[i][j];
while(q–)
{
int x1,x2,y1,y2;
scanf(“%d%d%d%d”,&x1,&y1,&x2,&y2);
printf(“%d\n”,s[x2][y2]-s[x2][y1-1] -s[x1-1][y2]+s[x1-1][y1-1]);
}
return 0;
}

****/