给你一个 n 行 m 列的矩阵 A ，下标从 1 开始，接下来有 q 次查询，每次查询输入 4 个参数 x1 , y1 , x2 , y2。
请输出以 (x1, y1) 为左上角，(x2,y2) 为右下角的子矩阵的和。
输入描述：
第一行包含三个整数 n，m，q。
接下来 n 行，每行 m 个整数，代表矩阵的元素
接下来 q 行，每行 4 个整数 x1，y1，x2，y2，分别代表这次查询的参数。
输出描述：
输出 q 行，每行代表一次查询的结果。
示例1：
输入：
3 4 3
1 2 3 4
3 2 1 0
1 5 7 8
1 1 2 2
1 1 3 3
1 2 3 4
输出：
8
25
32解题思路
一开始我有一个思路，虽然时间复杂度不是很好，其实就是借用了一维前缀和的思路，先开辟一个二维数组 prefix，然后将二维数组的每一行都进行一维前缀和，接着在多次查询中就需要遍历多列去获取每行的前缀和，累加起来，得到最后的前缀和！
虽然这种做法是可以的，但其实时间复杂度没有达到最优处理！所以我们要利用二维前缀和的思想，其实就是一个简单的二维动态规划问题！
那么我们就得想办法看看建立起一个状态转移方程，如下图所示，红色区域是我们要求的元素：
此时如果我们直接从 [x1, y1] 开始求的话，那是比较麻烦的，和我们上面那个思路是差不多的，所以我们不妨这样子想：我们要求的区间，其实可以将其从 [1, 1] 到 [x2, y2] 区间分为下面四个区域：
那我们想，能不能就求 [1, 1] 区间到 [i, j] 区间上的元素和，然后减去两个绿色区间的元素和以及蓝色区间的元素和，不就得到我们想要的红色区间的元素和了吗！
所以我们假设 dp[i][j] 表示从 [1, 1] 到 [i, j] 处的元素和。（其中我们规定从下标 1 开始遍历，这样子可以有效的防止越界问题）然后我们就对原数组进行遍历，将 dp 表进行填充，此时我们只要做一些拼接就可以了！
再遍历 dp 表之前，我们再简化一下，我们把蓝色区间和两个绿色区间分别合并起来，这样子得到两个大的绿色区间，就能和 [1, 1] 关联起来，就能使用这个状态表示了！
首先我们先来求蓝色区间元素和，很明显就能发现，根据状态表示可以得到其元素和就是 dp[i - 1][j - 1]。
然后就是竖向的这块绿色区间元素和，根据状态表示可以得到 dp[i][j - 1]。
接着就是横向的这块绿色区间的元素和，根据状态表示可以得到 dp[i - 1][j]。
因为两块绿色区间叠加起来之后，蓝色区间其实是重复了两次，所以我们要减去一个蓝色区间的元素和！
所以最后我们就能推出从 [1, 1] 到 [i, j] 区间的元素和 dp[i][j] = dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1] + arr[i][j]。
有了 dp 表之后，现在我们就要求目标区间的元素和了，也就是 [x1, y1] 到 [x2, y2] 区间的元素和，那和上面一样，只需要将整个区间分块来减去即可！
可以看出我们要求目标区间，其实就用 dp[i][j] 也就是从 [1, 1] 到 [x2, y2] 区间的元素和，减去两个大块的绿色区间，但是因为最后两块大的绿色区间都是需要减去的，而蓝色区间部分其实是叠加了两层，相当于被减了两次，所以我们还得加一次蓝色区间的元素和，才能抵消掉！
最后就能得到**目标区间的元素和就是 dp[i][j] - dp[i - 1][j] - dp[i][j - 1] + dp[i - 1][j - 1]**。
#include <iostream>
#include <vector>
using namespace std;
int main()
{
// 输入处理
int n, m, q;
cin >> n >> m >> q;
vector<vector<int>> arr(n + 1, vector<int>(m + 1));
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)
cin >> arr[i][j];
// 二维前缀和处理
vector<vector<long long>> prefix(n + 1, vector<long long>(m + 1));
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)
prefix[i][j] = prefix[i][j - 1] + prefix[i - 1][j] + arr[i][j] - prefix[i - 1][j - 1];
while(q--)
{
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
// 输出指定范围
cout << prefix[x2][y2] - prefix[x2][y1 - 1] - prefix[x1 - 1][y2] + prefix[x1 - 1][y1 - 1] << endl;
}
}