给我们一个 n×mn \times mn×m 的矩阵,矩阵中任意一点的左上角的点的数之和加上这个点的值为该点的二维前缀和 s[i][j]=∑i=1...ij=1...ja[i][j]s[i][j]=\sum_{i=1...i}^{j=1...j} a[i][j]s[i][j]=∑i=1...ij=1...j a[i][j].
那么我们应该怎么用公式求呢?
既然我们求出了每一个点对应的二维前缀和,那么如果需要求子矩阵的二维前缀和呢,该怎么求.
红色部分为所求区域,绿色和橙色是多余部分要减去,而灰色部分是多减了要加回来.
输入一个n行m列的整数矩阵,再输入q个询问,每个询问包含四个整数x1 y1 x2 y2,表示一个子矩阵的左上角坐标和右下角坐标.
对于每个询问输出子矩阵中所有数的和.
第一行包含三个整数n,m,q.
接下来n行,每行包含m个整数,表示整数矩阵.
共q行,每行输出一个询问的结果.
1≤nm≤10001≤nm≤10001≤nm≤1000
1≤q≤2000001≤q≤2000001≤q≤200000
1≤x1≤x2≤n1≤x1≤x2≤n1≤x1≤x2≤n
1≤y1≤y2≤m1≤y1≤y2≤m1≤y1≤y2≤m
−1000≤矩阵内元素的值≤1000−1000≤矩阵内元素的值≤1000−1000≤矩阵内元素的值≤1000