C++求子矩阵的和，要求如题

题目描述
给定一个M行N列的矩阵，要求你求得子矩阵(x1, y1), (x2, y2)的内所有元素的和。其中(x1, y1)和(x2, y2)是子矩阵的两个顶点。

输入
第一行输入包括三个数字M N Q。
接下来M行每行N个整数，表示需要处理的矩阵。
接下来Q行每行四个整数，表示子矩阵的方位。
输出
对于每一次询问，输出子矩阵内所有元素的和。

样例输入
4 3 2
1 2 3
4 5 6
7 8 9
10 11 12
0 0 3 2
0 0 1 1
样例输出
78
12
提示
1 <= M, N <= 1000
Q <= 1000

引用chatgpt部分指引作答：
运行结果如下：

img


#include <iostream>
using namespace std;

const int MAXN = 1005;
int m, n, q;
int a[MAXN][MAXN]; // 原矩阵
int s[MAXN][MAXN]; // 二维前缀和

int main() {
    cin >> m >> n >> q;

    // 读入原矩阵，同时计算二维前缀和
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            cin >> a[i][j];
            s[i + 1][j + 1] = s[i][j + 1] + s[i + 1][j] - s[i][j] + a[i][j];
        }
    }

    // 处理每个询问
    while (q--) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        int sum = s[x2 + 1][y2 + 1] - s[x1][y2 + 1] - s[x2 + 1][y1] + s[x1][y1];
        cout << sum << endl;
    }
    system("pause");
    return 0;
}

这个就是用双循环就好了啊
题目有问题啊，Q如果是1000的话，崩溃了吧。测试数据x,y是从0开始的啊

#include <iostream>
using namespace std;
int a[1000][1000];
int main()
{
    int M,N,Q,i,j,k;
    int x1,y1,x2,y2,sum=0;
    cin>>M>>N>>Q;
    for(i=0;i<M;i++)
        for(j=0;j<N;j++)
            cin>>a[i][j];
    for(i=0;i<Q;i++)
    {
        cin>>x1>>y1>>x2>>y2;
        sum=0;
        for(j=x1;j<=x2;j++)
            for(k=y1;k<=y2;k++)
                sum += a[j][k];
        cout<<sum<<endl;
    }
    return 0;
}

引用chatGPT作答，这是一道二维前缀和的经典问题，可以用动态规划求解。具体地，我们可以先预处理一个二维前缀和数组 sum，其中 sum[i][j] 表示矩阵左上角为 (0, 0)，右下角为 (i, j) 的子矩阵的所有元素之和。这个数组可以用以下的递推式计算：

img


其中 matrix 是原始的输入矩阵。计算完 sum 后，对于每一次询问，我们可以通过以下公式计算子矩阵的和：

img


其中 answer 就是所求的子矩阵的和。

下面是 C++ 的实现代码：

#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 1005;

int matrix[MAXN][MAXN], sum[MAXN][MAXN];

int main() {
    int m, n, q;
    cin >> m >> n >> q;

    // 读入矩阵并计算二维前缀和
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            cin >> matrix[i][j];
            if (i == 0 && j == 0) {
                sum[i][j] = matrix[i][j];
            } else if (i == 0) {
                sum[i][j] = matrix[i][j] + sum[i][j-1];
            } else if (j == 0) {
                sum[i][j] = matrix[i][j] + sum[i-1][j];
            } else {
                sum[i][j] = matrix[i][j] + sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1];
            }
        }
    }

    // 处理每个询问
    while (q--) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;

        int answer = sum[x2][y2];
        if (x1 > 0) answer -= sum[x1-1][y2];
        if (y1 > 0) answer -= sum[x2][y1-1];
        if (x1 > 0 && y1 > 0) answer += sum[x1-1][y1-1];

        cout << answer << endl;
    }

    return 0;
}

这段代码首先读入矩阵和询问的数量，然后使用上面的算法计算二维前缀和 sum。最后，它处理每个询问，并按照上述公式计算子矩阵的和，最终输出答案。

希望这个代码能帮到您！



```c++

#include <iostream>

using namespace std;

const int N = 1007;

int a[N][N],s[N][N];

int main() {
    int n,m;long q;
    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)
            s[i][j]= s[i][j-1] + s[i-1][j] - s[i-1][j-1] + a[i][j];

   
    int x1,y1,x2,y2;
    while (q--){
        cin >> x1 >> y1 >> x2 >> y2;
        cout << s[x2+1][y2+1] - s[x1][y2+1] - s[x2+1][y1] + s[x1][y1] << "\n";
    }

    return 0;
}
这是我自己的代码，是答案错误50%

```