我们用map[i][j]记录每一格的值、用DP[i][j]表示（1，1）这个点与（i,j）这个点两个点分别为左上角和右下角所组成的矩阵内的数的和。

转移方程：DP[i][j]=DP[i-1][j] + DP[i][j-1] - DP[i-1][j-1] + map[i][j]

图片说明
DP[i][j]可以由DP[i-1][j]、DP[i][j-1]两块构成,注意：
1.有一块矩阵重复了，我们要减掉这一块-> DP[i-1][j-1]
2.有一小块没有加上，也就是map[i][j]这一个点，所以我们要再加上map[i][j]这一格的数.

那么如何计算以(x1,y1)为左上角，以(x2,y2)为右上角的矩阵和呢？

图片说明
转移方程：任意矩阵和=DP[x2][y2] - DP[x1][y2] - DP[x2][y2] + DP[x1][y1]

实现代码：

#include<iostream>
#include<cstring>
using namespace std;
int dp[2000][2000];
int map[2000][2000];
int main()
{
    int m,n,k;     //所给的矩阵是n*m的,有k组查询
    cin >> n >> m >> k;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin >>map[i][j];
        }
    }
    memset(dp,0,sizeof(dp));
    for(int i=1;i<=n;i++)//预处理一波
    {
        for(int j=1;j<=m;j++)
        {
            dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + map[i][j];
        }
    }
    for(int i=1;i<=k;i++)//接受查询
    {
        int x1,x2,y1,y2;
        cin >>x1>>y1>>x2>>y2;
        cout << dp[x2][y2] + dp[x1-1][y1-1] - dp[x1-1][y2] - dp[x2][y1-1] << endl;//O（1）查询
    }
    return 0;
}