[ BOJ ] 1275 : 커피숍2 ( GOLD 1 ) / C

문제

모두 알다시피 동호는 커피숍의 마담이다. (마담이 무엇인지는 본인에게 물어보도록 하자.)

어느 날 커피숍의 손님 A씨가 동호에게 게임을 하자고 했다.

그 게임은 다음과 같은 규칙을 갖는다.

N개의 정수가 있으면, 동호는 다음과 같이 말한다. “3~7번째 수의 합은 무엇이죠?” 그러면 상대방은 “그 답은 000입니다. 그리고 8번째 수를 2로 고치도록 하죠” 그러면 동호는 “네 알겠습니다.”라고 한 뒤에 다시 상대방이 동호가 했던 것처럼 “8~9번째 수의 합은 무엇이죠?”라고 묻게된다. 이 것을 번갈아 가면서 반복하는 게임이다.

당신은 이 게임의 심판 역을 맡았다. 요컨대, 질문에 대한 답들을 미리 알아야 한다는 것이다.

당신의 머리가 출중하다면 10만개 가량 되는 정수와 10만턴 정도 되는 게임을 기억할 수 있을 것이다. 몇판 이 게임을 즐기던 동호는 많은 사람들이 이 게임을 하기를 바라게 되었고, 당신에게 심판 프로그램을 구현해달라고 요청했다.

입력

첫째 줄에 수의 개수 N과 턴의 개수 Q가 주어진다.(1 ≤ N, Q ≤ 100,000) 둘째 줄에는 처음 배열에 들어가 있는 정수 N개가 주어진다. 세 번째 줄에서 Q+2번째 줄까지는 x y a b의 형식으로 x~y까지의 합을 구하여라, a번째 수를 b로 바꾸어라 라는 뜻의 데이터가 주어진다.

입력되는 모든 수는 -2^31보다 크거나 같고, 2^31-1보다 작거나 같은 정수이다.

출력

한 턴마다 구한 합을 한 줄마다 한 개씩 출력한다.

풀이 과정

세그먼트 트리를 이용해 풀이했다.

#include <stdio.h>

long long int arr[100000];
long long int tree[400000];

long long int init(int start, int end, int index) {
	if (start == end) {
		tree[index] = arr[start];
		return tree[index];
	}

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

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

	int mid = (start + end) / 2;
	return interval_sum(start, mid, index * 2, left, right) + interval_sum(mid + 1, end, index * 2 + 1, left, right);
}

void update(int start, int end, int index, int what, long long  int val) {
	if (what < start || end < what)
		return;
	tree[index] += val;
	if (start == end)
		return;

	int mid = (start + end) / 2;
	update(start, mid, index * 2, what, val);
	update(mid + 1, end, index * 2 + 1, what, val);
}

int main(void) {
	int n, q;
	scanf("%d %d", &n, &q);
	for (int i = 0; i < n; i++) scanf("%lld", &arr[i]);

	init(0, n - 1, 1);
	for (int i = 0; i < q; i++) {
		int x, y, a;
		long long int b;
		scanf("%d %d %d %lld", &x, &y, &a, &b);
		int mins, maxs;
		if (x < y) {
			mins = x;
			maxs = y;
		}
		else {
			mins = y;
			maxs = x;
		}
		printf("%lld\n", interval_sum(0, n - 1, 1, mins - 1, maxs - 1));
		long long int v = b - arr[a - 1];
		update(0, n - 1, 1, a - 1, v);
		arr[a - 1] = b;
	}
	return 0;
}