[BOJ/C++] 11660 구간 합 구하기5

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]$ 입니다.

// boj s1 11660
// 구간 합 구하기5

#include <iostream>
#include <vector>

using namespace std;

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int N, M;
	cin >> N >> M;

	vector<vector<int>> A(N + 1, vector<int>(N + 1, 0));
	vector<vector<int>> D(N + 1, vector<int>(N + 1, 0));

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

	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
			D[i][j] = D[i][j - 1] + D[i - 1][j] - D[i - 1][j - 1] + A[i][j];
	}

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

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

	return 0;
}