题解 | #【模板】二维前缀和#

解题思路：

• 在输入过程中直接计算，记录从坐标（0，0）到当前坐标（x,y)所构成矩形的和，查询$Q_{(x1,y1)to(x2,y2)}=SU{M}_{(x2,y2)}-SU{M}_{(x1-1,y2)}-SU{M}_{(x2,y1-1)}+SU{M}_{(x1-1,y1-1)}Q\_\{(x1,y1)\; to\; (x2,y2)\}\; =\; SUM\_\{(x2,y2)\}\; -\; SUM\_\{(x1-1,y2)\}\; -\; SUM\_\{(x2,y1-1)\}\; +\; SUM\_\{(x1-1,y1-1)\}$.

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n, m , q;
    cin>>n>>m>>q;
    long long tmpv;
    vector<vector<long long>> v(n+1,vector<long long>(m+1, 0));
    for(int i = 1; i <= n; ++i){
        long long sum = 0;
        for(int j = 1; j <= m; ++j){
            scanf("%lld",&tmpv);
            sum += tmpv;
            v[i][j] = sum + (i>1? v[i-1][j]: 0);

        }
    }
    for(int i = 0; i < q; ++i){
        int x1, y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        cout<<v[x2][y2] - v[x2][y1-1] - v[x1-1][y2] + v[x1-1][y1-1]<<endl;
    }
    return 0;
}