描述
对于给定的 n 行 m 列的矩阵
，你需要构建一个能够维护子矩阵和信息的数据结构，使得其能支持：
子矩阵和查询：输出左上角为(x1,y1) 、右下角为(x2,y2) 的子矩阵的元素之和，即。
输入描述：
第一行输入三个整数 n,m,q(1≦n,m,q,n×m≦5×10^5) 代表矩阵的长宽、操作次数。
此后 n 行，每行输入 m 个整数 a1,a2,…,am(−10^9≦ai≦10^9) 代表初始矩阵。
此后 q 行，每行输入四个整数 x1,y1,x2,y2(1≦x1≦x2≦n; 1≦y1≦y2≦m) 代表子矩阵和查询。输出描述：
对于每一次询问，在一行上输出一个整数代表子矩阵和。
示例1
输入：
3 4 3 1 2 3 4 3 2 1 -2 1 5 7 8 1 1 2 2 1 1 3 3 1 2 3 4输出：
8 25 30说明：
对于第一次询问，如公式所示，即求解红色部分元素和， ； 对于第二次询问，如公式所示， 。
一、问题分析
首先读题，仔细看描述中的内容，发现需求是
1.给定一个m行n列的矩阵，
2.以及一个操作次数q
3.每次操作给定4个整数x1,y1,x2,y2
4.每次操作求，以x1，y1为左上角，x2，y2为右下角的子矩阵的元素和
二、解题思路
1.首先读取矩阵matrix[m][n]
2.读取的同时，维护一张矩阵的从左上角0，0到每一个坐标的和的矩阵和矩阵
3.如何得到矩阵和的值？matrixsum[x][y] = matrixsum[x - 1][y] + matrixsum[x][y - 1] - matrixsum[x - 1][y - 1] + matrix[x][y]
4.如何得到x1，y1为左上角，x2，y2为右下角的子矩阵的元素和？
sum = matrixsum[x2][y2] - matrixsum[x1 - 1][y2] - matrixsum[x2][y1 -1] + matrixsum[x1 - 1][y1 - 1]
三、具体步骤
使用的语言是C
#include <stdio.h>
#define ll long longint main() {int n, m, q;if (scanf("%d %d %d", &n, &m, &q) != EOF) {ll matrix[n + 1][m + 1], matrixsum[n + 1][m + 1];for(int i = 0; i < n; i++) {matrixsum[0][i] = 0;matrixsum[i][0] = 0;}for(int i = 1; i <= n; i++) {for(int j = 1; j <= m; j++) {if(scanf("%lld", &matrix[i][j]) != EOF) {matrixsum[i][j] = matrixsum[i - 1][j] + matrixsum[i][j - 1] - matrixsum[i - 1][j - 1] + matrix[i][j];} else printf("error2\n");}}while(q--) {int x1, y1, x2, y2;if(scanf("%d %d %d %d", &x1, &y1, &x2, &y2) != EOF) {printf("%lld\n", matrixsum[x2][y2] - matrixsum[x1 -1][y2] - matrixsum[x2][y1 - 1] + matrixsum[x1 - 1][y1 - 1]);} else printf("error3\n");}} else printf("error1\n");return 0;
}
