题目描述

原题

题目大意&链接

在一个给定的 n 行 m 列矩阵中，查询出子矩阵的和。

输入输出样例：
输入：

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

输出：

17
27
21

详情：ac_796子矩阵的和

解题思路

子矩阵的和需要注意2点。

  1. 计算前缀和：
    示意图1 
    //计算前缀和
    res[i][j] = res[i-1][j] + res[i][j-1] - res[i-1][j-1] + arr[i][j];
  2. 计算矩阵区间和：
    示意图2 
    //计算矩阵区间和
    cout<<res[x2][y2] - res[x1-1][y2] - res[x2][y1-1] + res[x1-1][y1-1]<<endl;

完整代码

#include<iostream>

using namespace std;

const int N = 1010;

int n, m, q;
int arr[N][N];
int res[N][N] = {0}; //res[i, j] 为第i行j列格子左上部分所有元素的和

int main()
{
    scanf("%d %d %d", &n, &m, &q);
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            scanf("%d", &arr[i][j]);
            //计算前缀和（以res[3][2]为例）
            res[i][j] = res[i-1][j] + res[i][j-1] - res[i-1][j-1] + arr[i][j];
        }
    }
    
    while(q--)
    {
        int x1, y1, x2, y2;
        scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
        //计算矩阵区间和
        cout<<res[x2][y2] - res[x1-1][y2] - res[x2][y1-1] + res[x1-1][y1-1]<<endl; 
    }
    return 0;
}

时间和空间复杂度

时间复杂度：O(n * m + q)
空间复杂度：O(n * m)