希望的田野

题目

田野里总是充满了希望。

一片 n 行 m 列的田野，每一块都有一个希望值。每次询问给出左上角 (x1, y1) 和右下角 (x2, y2)，求该矩形范围内所有希望值的总和。

输入：第一行三个整数 n、m、q，q 表示询问次数。接下来 n 行每行 m 个整数为田野的希望值。之后 q 行，每行四个整数 x1、y1、x2、y2。
输出：共 q 行，每行输出对应矩形范围的希望值总和。

样例1：

3 5 4
1 1 6 7 4
6 10 4 9 9
2 6 7 3 7
1 2 2 4
2 4 3 5
2 2 3 5
1 3 2 4

37
28
55
26

样例2：

5 4 2
2 3 5 4
6 5 6 4
9 4 5 1
3 6 5 7
3 6 5 4
1 2 2 3
3 4 5 4

19
12

思路

用二维前缀和预处理：pre[i][j] 表示从 (1,1) 到 (i,j) 矩形内所有值的总和，建表公式为 pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + a[i][j]。 查询 (x1,y1) 到 (x2,y2) 的子矩形和时，利用容斥原理一步得出： pre[x2][y2] - pre[x1-1][y2] - pre[x2][y1-1] + pre[x1-1][y1-1]，每次查询 O(1)。

#include<bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n,m,q;
    cin>>n>>m>>q;

    vector<vector<long long>> pre(n+1, vector<long long>(m+1,0));
    for(int c1=1;c1<=n;c1++){
        for(int c2=1;c2<=m;c2++){
            int value;
            cin>>value;
            pre[c1][c2]=pre[c1-1][c2]+pre[c1][c2-1]-pre[c1-1][c2-1]+value;
        }
    }

    for(int c=0;c<q;c++){
        long long x1,y1,x2,y2,output;
        cin>>x1>>y1>>x2>>y2;
        output=pre[x2][y2]-pre[x1-1][y2]-pre[x2][y1-1]+pre[x1-1][y1-1];
        cout<<output<<"\n";
    }
    return 0;
}

复杂度分析

• 时间复杂度：O(nm + q)，建表 O(nm)，每次查询 O(1)。
• 空间复杂度：O(nm)，前缀和二维数组。

← 返回菜鸟的coding