[BOJ] 2042 구간 합 구하기

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

2042번: 구간 합 구하기

문제

어떤 N개의 수가 주어져 있다. 그런데 중간에 수의 변경이 빈번히 일어나고 그 중간에 어떤 부분의 합을 구하려 한다. 만약에 1,2,3,4,5 라는 수가 있고, 3번째 수를 6으로 바꾸고 2번째부터 5번째까지 합을 구하라고 한다면 17을 출력하면 되는 것이다. 그리고 그 상태에서 다섯 번째 수를 2로 바꾸고 3번째부터 5번째까지 합을 구하라고 한다면 12가 될 것이다.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄까지 N개의 수가 주어진다. 그리고 N+2번째 줄부터 N+M+K+1번째 줄까지 세 개의 정수 a, b, c가 주어지는데, a가 1인 경우 b(1 ≤ b ≤ N)번째 수를 c로 바꾸고 a가 2인 경우에는 b(1 ≤ b ≤ N)번째 수부터 c(b ≤ c ≤ N)번째 수까지의 합을 구하여 출력하면 된다.

입력으로 주어지는 모든 수는 -2^63보다 크거나 같고, 2^63-1보다 작거나 같은 정수이다.

5 2 2
1
2
3
4
5
1 3 6
2 2 5
1 5 2
2 3 5

출력

첫째 줄부터 K줄에 걸쳐 구한 구간의 합을 출력한다. 단, 정답은 -2^63보다 크거나 같고, 2^63-1보다 작거나 같은 정수이다.

17
12

---

이웃집이 풀어본 문제를 나도 풀어보려다가 어려워서 때려치고

새로운 개념을 공부해볼까해서 풀어본 세그먼트 트리 문제다.

 

문제는 세그먼트 트리 개념 그 자체다.

빈번히 값이 수정되는 배열의 구간 합을 구하는 경우엔 매번 새로 O(n) 시간을 들여서 

구간 합을 계산하면 시간이 많이 걸리게된다.

그래서 등장한 것이 세그먼트 트리인데, 얘는 구간을 반으로 나눠서 미리 구간 합을 구해놓는다.

인덱스를 다루는게 힙이랑 상당히 비슷하다.

 

어찌저찌해서 문제는 맞았는데 시간이 1000ms가 넘게 나왔다.

원래 이런 문제인가 해서 다른 사람들이 걸린 시간을 확인했는데 그렇지 않아 보였다.

찾다보니 백준 사이트에 이런 글도 올라와있길래 다시 제출해보았다.

https://www.acmicpc.net/blog/view/9

세그먼트 트리 (Segment Tree)

그래서 걸린 시간은 내 코드보다 4배 정도 빠른 240ms.

가장 빠른 사람은 16ms 정도 걸렸지만 그 정도는 바라지도 않았다(이 사람은 펜윅트리라는 걸 사용한듯).

 

도대체 뭐가 문제길래 싶어서 나는 이렇게 오래 걸리나 코드를 찬찬히 살펴봤다.

함수들에는 딱히 문제가 없어보여서 일단 cin을 scanf로 바꿔보았다.

그랬더니 1020ms에서 228ms로 시간이 대폭 감소했다.

얼핏 듣기로 cin이 시간이 많이 걸린다고 들은 것 같긴한데 이렇게 오래 걸릴 줄은 몰랐다.

cin, cout을 최적화하는 방법을 사용하면 시간이 얼마나 줄어들까해서 그것도 한번 해봤다.

이렇게 하니까 140ms가 걸렸다.  신기하다.

 

https://hegosumluxmundij.tistory.com/54

ios::sync_with_stdio , cin.tie , cout.tie 사용법과 설명, 속도 비교

 

 

#include <iostream>

#define MAX 1000000

int N, M, K;
long long numbers[MAX];
long long tree[4 * MAX + 1];

long long init(int start, int end, int node) {
	if (start == end) return tree[node] = numbers[start];

	int mid = (start + end) / 2;

	return tree[node] = init(start, mid, node * 2) + init(mid + 1, end, node * 2 + 1);
}

long long sum(int start, int end, int node, int left, int right) {
	if (right < start || end < left) return 0;
	if (left <= start && end <= right) return tree[node];

	int mid = (start + end) / 2;

	return sum(start, mid, node * 2, left, right) + sum(mid + 1, end, node * 2 + 1, left, right);
}

void update(int start, int end, int node, int index, long long dif) {
	if (index < start || index > end) return;

	tree[node] += dif;

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

int main() {
	scanf("%d %d %d", &N, &M, &K);

	for (int i = 0; i < N; i++)
		scanf("%lld", &numbers[i]);

	init(0, N - 1, 1);

	int a;
	for (int i = 0; i < M + K; i++) {
		scanf("%d", &a);

		if (a == 1) {
			int b;
			long long c;

			scanf("%d %lld", &b, &c);
			
			update(0, N - 1, 1, b - 1, c - numbers[b - 1]);
			numbers[b - 1] = c;
		}

		else {
			int b, c;

			scanf("%d %d", &b, &c);
			std::cout << sum(0, N - 1, 1, b - 1, (int)c - 1) << "\n";
		}
	}

	return 0;
}

 

후기)

입출력이 많으면 cin, cout은 생각보다 더 오래 걸린다.

세그먼트 트리 공부하려고 했는데 배보다 배꼽이 더 컸던 것 같다.

다음엔 펜윅 트리도 공부해봐야겠다.

잠깐 읽어보니까 마지막 1의 위치를 알아야하는 것부터 너무 어지럽다;

생각해보니 위상정렬하기로 해놓고 아직도 안 했다 ㅎ