문해기 1번 과제

어렵지 않게, (4, 4)부터 (4, 4)까지의 합을 구하면 1이다. 

입력 

표준입력으로 입력이 주어진다. 첫 줄에는 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. N은 1 이상 1024 이하, M은 1 이상 100,000 이하이다. 그 다음 N 줄에는 표에 대한 정보가 주어진다. 한 줄에는 N개의 숫자가 사이에 공백을 두고 주어진다. 이 수들은 모두 1 이상 1,000 이하인 정수이다. 그 다음 M개의 줄에는 각각의 줄마다 a b c d 4개의 정수가 주어지는데, 이들은 모두 1 이상 N 이하이며, a는 c 이하, b는 d 이하이다. 이는 (a, b)부터 (c, d)까지의 직사각형 부분에 대한 합을 구하라는 것이다. 

출력 

입력에서 각 줄에 주어진 a b c d마다 해당하는 합을 한 줄에 출력한다. 따라서 답은 총 M줄이다. 

제출 

하나의 .c/.cpp/.java 파일을 제출한다. 

예제 입력 

4 2

0 1 0 1 

1 1 0 1

1 0 1 0

1 1 2 1

2 2 3 4

4 4 4 4 

예제 출력

3 

1

 

2차원 부분합 문제이다. 세그먼트트리로 풀었다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

class SegmentTree {
private:
	vector<long long> Nodes;
	vector<long long> input;
	long long init(int index, int start, int end) {
		if (start == end) {
			Nodes[index] = input[start];
		}
		else {
			Nodes[index] = init(index * 2 + 1, start, (start + end) / 2) + init(index * 2 + 2, (start + end) / 2 + 1, end);
		}
		return Nodes[index];
	}

public:
	SegmentTree(int N, vector<long long> input) {
		int height = (int)ceil(log2(N));
		int tree_size = (1 << (height + 1));
		Nodes.resize(tree_size+1,0);

		this->input = input;
		init(0, 0, N - 1);
	}

	long long sum(int index, int start, int end, int left, int right) {
		if (start > right || end < left)
			return 0;
		else if (start >= left && end <= right)
			return Nodes[index];
		else {
			int middle = (start + end) / 2;
			return sum(2 * index + 1, start, middle, left, right) + sum(2 * index + 2, middle + 1, end, left, right);
		}
	}
	void update(int changed_index, long long diff, int index, int start, int end)
	{
		if (changed_index < start || changed_index > end)
			return;

		Nodes[index] += diff;

		if (start != end) {
			int mid = (start + end) / 2;
			update(changed_index, diff, index * 2 + 1, start, mid);
			update(changed_index, diff, index * 2 + 2, mid + 1, end);
		}
	}
};

int main() {
	ios_base::sync_with_stdio(NULL); cin.tie(NULL); cout.tie(NULL);
	int N, M;
	cin >> N >> M;
	vector<vector<long long>> input(N+1);
	vector<SegmentTree> arr;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			input[i].push_back(0);
		}
	}
	for (int i = N-1; i >= 0; i--) {
		for (int j = 0; j < N; j++) {
			int tmp;
			cin >> tmp;
			input[i][j] = tmp;
		}
	}

	for (int i = 0; i < N; i++) {
		SegmentTree tmp = SegmentTree(N, input[i]);
		arr.push_back(tmp);
	}

	for (int i = 0; i < M; i++) {
		int a, b, c, d;
		long long ans = 0;
		cin >> a >> b >> c >> d;
		int ymax = max(b, d)-1;
		int ymin = min(b, d)-1;
		int xmax = max(a, c)-1;
		int xmin = min(a, c)-1;
		for (int j = ymin; j <= ymax; j++) {
			ans += arr[j].sum(0, 0, N - 1, xmin, xmax);
		}
		cout << ans << endl;
	}

	return 0;
}