11660번 (silver 1)

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

구간합 알고리즘에서 조금 더 심화된 문제이다. 일반적으로 구간합은 1차원으로 생각하는데 2차원 넓이로 구간합을 계산하기를 요구하고 있다.

 

#include <iostream>
#include <vector>

using namespace std;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, query;
	cin >> N >> query;
	vector<vector<int>> arr_sum(N + 1, vector<int>(N + 1, 0));
	
	for (int i = 1; i <= N; ++i) {
		for (int j = 1; j <= N; ++j) {
			int temp;
			cin >> temp;
			arr_sum[i][j] = arr_sum[i][j - 1] + arr_sum[i - 1][j] + temp - arr_sum[i - 1][j - 1];
		}
	}

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

		cout << arr_sum[x2][y2] - arr_sum[x2][y1 - 1] - arr_sum[x1 - 1][y2] + arr_sum[x1 - 1][y1 - 1] << "\n";
	}

	return 0;
}