思路

• 容斥原理
  ①.简单来二位前缀和的递推公式就是t[x] [y]=t[x-1] [y]+t[x] [y-1]-t[x-1] [y-1]
  ②.如何利用前缀和数组来计算出想要的子矩阵的和呢？还是使用容斥原理
  比如说计算1 3 3 4的子矩阵的和，他的算法简单来说就是t[3] [4]-t[3] [2]-t[0] [4]+t[0] [2]
  也就是x1 y1 x2 y2 他的算法简单就是t[x2] [y2]-t[x2] [y1-1]-t[x1-1] [y2]+t[x1-1] [y1-1]

代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010;
int a[N][N];
int n,m,q;
int main()
{
    cin>>n>>m>>q;
    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++)
        {
            a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+a[i][j];
        }
    }
    while(q--)
    {
        int x1,x2,y1,y2;
        cin>>x1>>y1>>x2>>y2;
        cout<<a[x2][y2]-a[x1-1][y2]-a[x2][y1-1]+a[x1-1][y1-1]<<endl;
    }
    return 0;
}