https://www.acmicpc.net/problem/15724

핵심 아이디어

<aside> 💡

2차원 누적합 문제

</aside>

코드

#include <bits/stdc++.h>
#define FASTIO ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
using namespace std;
typedef long long ll;

int n, m;
ll psum[1030][1030];

signed main()
{
    FASTIO;
    cin >> n >> m;
    for(int i = 1; i<=n; i++){
        for(int j = 1; j<=m; j++){
            cin >> psum[i][j];
        }
    }

    for(int i = 1; i<=n; i++){
        for(int j = 1; j<=m; j++){
            psum[i][j] += psum[i][j-1] + psum[i-1][j] - psum[i-1][j-1];
        }
    }

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