[백준] 11659번 구간 합 구하기 4

11659번: 구간 합 구하기 4

그냥 cin cout 쓰면 무조건 시간 초과 난다.

ios_base::sync_with_stdio(false);
	cin.tie(NULL);

를 적어주거나 scanf printf를 써야 한다.

 

DP와 세그먼트 트리,

두 가지  방식으로 풀어 보았다.

 

1. DP

i번째 칸에 1번째 수부터 i번째 수까지 더한 값을 저장해놓고

a부터 b까지의 합을 출력할 때는

b번째 값에서 a - 1번째 값을 빼서 출력한다.

#include <iostream>
using namespace std;
int N, M, a, b, num;
int arr[100002];
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		cin >> num;
		arr[i] = arr[i - 1] + num;
	}
	for (int i = 0; i < M; i++) {
		cin >> a >> b;
		cout << arr[b] - arr[a - 1] << "\n";
	}
	return 0;
}

 

2. 세그먼트 트리

구간 합 구하기와 같은 방식으로 풀었다.

#include <iostream>
using namespace std;
int N, M, a, b;
int arr[100001], tree[262150];
int Init(int left, int right, int idx) {
	if (left == right) return tree[idx] = arr[left];
	int mid = (left + right) / 2;
	return tree[idx] = Init(left, mid, idx * 2) + Init(mid + 1, right, idx * 2 + 1);
}
int Find(int left, int right, int idx) {
	if (left >= a && right <= b) return tree[idx];
	if (left > b || right < a) return 0;
	int mid = (left + right) / 2;
	return Find(left, mid, idx * 2) + Find(mid + 1, right, idx * 2 + 1);
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> N >> M;
	for (int i = 0; i < N; i++) cin >> arr[i];
	Init(0, N - 1, 1);
	for (int i = 0; i < M; i++) {
		cin >> a >> b;
		a -= 1, b -= 1;
		cout << Find(0, N - 1, 1) << "\n";
	}
	return 0;
}