一. 题目

二. 理论

三. 代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N=1e3+10;

int n, m, q;

class PrefixAnd
{
public:
    int s[N][N];//前缀和数组，最初值是原数组值
public:
    PrefixAnd()
    {
        initIO();
    }

    void initIO()
    {
        // 关闭输入输出缓存，使效率提升
        ios::sync_with_stdio(false);
        // 解除cin和cout的默认绑定，来降低IO的负担使效率提升
        cin.tie(nullptr);
        cout.tie(nullptr);
    }

    //预处理s数组使其变成前缀和数组
    void initS()
    {
        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];
    }

    //得到左上角点为(x1, y1)到右下角点(x2, y2)的子矩阵和
    int getPa(int x1, int y1, int x2, int y2)
    {
        return s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1];
    }
}pa;

int main()
{
    cin>>n>>m>>q;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            cin>>pa.s[i][j];

    pa.initS();//预处理前缀和数组
    while(q--)
    {
        int x1, y1, x2, y2;
        cin>>x1>>y1>>x2>>y2;
        cout<<pa.getPa(x1, y1, x2, y2)<<endl;
    }
}