[BOJ/C++] 15724 주지수

2차원 배열의 구간 합을 구하는 문제로 $(X1, Y1)$ 에서 $(X2, Y2)$ 까지의 합을 구하는 문제입니다.

먼저 숫자 배열로부터 1행, 1열의 구간합을 구합니다.

구한 1행 1열의 구간 합으로 $(2,2)$의 구간 합을 구합니다.

여기서 구간 합을 구하기 위한 식은 $D[i][j] = D[i][j-1] + D[i-1][j] - D[i-1][j-1] + A[i][j]$ 입니다.

문제에 주어진 $(2,2)$에서 $(3,4)$ 까지의 구간 합을 구하기 위해선 다음과 같습니다

즉, $(X1, Y1)$ 에서 $(X2, Y2)$ 까지의 구간 합은 $D[X2][Y2] - D[X1-1][Y2] - D[X2][Y1-1] + D[X1-1][Y1-1]$ 입니다.

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <string>
#include <climits>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>

using namespace std;

using int32 = long;
using int64 = long long;

static vector<vector<int>> v;
static vector<vector<int>> S;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int N, M;
    cin >> N >> M;

    v.resize(N+1, vector<int>(M+1, 0));
    S.resize(N+1, vector<int>(M+1, 0));

    for(int i=1; i<=N; i++)
    {
        for (int j = 1; j <= M; j++)
            cin >> v[i][j];
    }

    // Init PrefixSum
    for(int i=1; i<=N; i++)
    {
	    for(int j=1; j<=M; j++)
	    {
            S[i][j] = S[i - 1][j] + S[i][j - 1] -S[i-1][j-1] + v[i][j];
	    }
    }


    int T;
    cin >> T;

    for(int i=0; i<T; i++)
    {
        int y1, x1, y2, x2;
        cin >> y1 >> x1 >> y2 >> x2;

        cout << S[y2][x2] - S[y2][x1-1] - S[y1-1][x2] + S[y1-1][x1-1] << '\n';
    }



    return 0;
}