题目描述

给定一个矩阵，对每个输入的子矩阵左上角坐标和右下角坐标，请输出该子矩阵的所有元素之和；

样例

3 4 3
1 7 2 4
3 6 2 8
2 1 2 3 //矩阵到此结束，下面三行是查询
1 1 2 2
2 1 3 4
1 3 3 4

算法1

子矩阵和(前缀和变体) $O(n*m)$

此题做法与前缀和相同，只是变为了二维矩阵，对每一个输入的子矩形来说，都有将大矩形{(0,0), (x2,y2)}从(x1,y1)处分为四个小矩形，所求矩形即为右下角的小矩形，而其余矩形都可以看作与原点(0,0)为左上角的矩形，即有共同起点，则可通过前缀和方式进行计算；

时间复杂度 $O(n*m)$

建立矩形数组及子矩形和数组需要$O(n*m)$;
对每个查询都是常数级O(1);
若算上查询，则时间复杂度可看作$O(n*m+q)$ ;

参考文献

C++ 代码

#include<iostream>
using namespace std；

const int N = 1002;
int a[N][N], s[N][N];       //全局变量定义时自动初始化为0；

int main()
{
    int n, m, q;
    cin>>n>>m>>q;
    for(int i = 1; i <= n; ++i)    //起始设为1可以避免将边界单独领出来讨论
        for(int j = 1; j <= m; ++j){
            scanf("%d", &a[i][j]);
            s[i][j] = a[i][j] + s[i-1][j] + s[i][j-1] - s[i-1][j-1];   //建立时因为是子矩形和，所以两个加一个减
        }//将子矩形和数组的建立与矩形数组整合在一起，边输入边建；
    while(q--){
        int x1, y1, x2, y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        printf("%d\n", s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1]);//输出时减去两个大点矩形再加上公共部分；
    }
    return 0;
}