백준 1275: 커피숍2

문제 요약

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

당신에게 질문에 대한 답들을 미리 아는 심판 로그램을 구현해달라고 요청했다.

문제 분류

• 자료 구조
• 세그먼트 트리

문제 풀이

어떠한 구간 사이에서 일관성있는 연산과 수정을 반복하는 특징을 갖고 있으므로 세그먼트 트리 자료 구조로 풀었다.

construct(int l, int r, int idx)에서는 세그먼트 트리의 구축을 하는 함수이다. 재귀 호출과 그 합으로 구현하였다. 리프 노드의 시작 인덱스를 몰라도 된다.

update(int l, int r, int loc, int idx, int val)에서는 l~r사이의 idx의 값을 변경하는데, 그 실제 인덱스 값 seg[loc]의 값을 val로 수정하는 함수이다. 현재 탐색 중인 범위가 idx를 벗어날 경우 현재의 범위의 구간 합을 반환하여 시간을 줄였다.

sum(int L, int R, int l, int r, int idx)에서는 L~R 범위의 합을 반환하는 함수이다. 현재 범위인 l~r이 그 범위를 벗어날 경우 0을 리턴하고, 범위 안에 들어갈 경우는 그 구간 합을, 이외의 경우에는 재귀로 돌려주었다.

나는 세그먼트 트리의 인덱스가 0부터 시작하는 것으로 파악하였으므로 문제의 모든 인덱스 입력을 1감소하여야 한다. 그렇게 in1~in2까지의 구간 합을 출력하고, in3위치의 값을 in4로 수정한다.

입력 시에 in1이 in2보다 항상 작게끔 만들어주었다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>

using namespace std;

long long seg[400000];
int n, ary[100000];

long long construct(int l, int r, int idx)
{
	if (l == r) seg[idx] = ary[l];
	else {
		int mid = (l + r) / 2;
		seg[idx] = construct(l, mid, idx * 2 + 1) + construct(mid + 1, r, idx * 2 + 2);
	}
	return seg[idx];
}

long long update(int l, int r, int loc, int idx, int val)
{
	if (idx < l || idx > r) return seg[loc];
	if (l == r) {
		if (l == idx) seg[loc] = val;
		return seg[loc];
	}
	int mid = (l + r) / 2;

	seg[loc] = update(l, mid, loc * 2 + 1, idx, val) + update(mid + 1, r, loc * 2 + 2, idx, val);
	return seg[loc];
}

long long sum(int L, int R, int l, int r, int idx)
{
	if (l > R || r < L) return 0;
	if (L <= l && R >= r) return seg[idx];
	int mid = (l + r) / 2;
	return sum(L, R, l, mid, idx * 2 + 1) + sum(L, R, mid + 1, r, idx * 2 + 2);
}

int main()
{
	int q, in1, in2, in3, in4;
	scanf("%d%d", &n, &q);

	for (int i = 0; i < n; i++)
		scanf("%d", ary + i);

	construct(0, n - 1, 0);
	for (int i = 0; i < q; i++) {
		scanf("%d%d%d%d", &in1, &in2, &in3, &in4);
		in1--, in2--, in3--;
		if (in1 > in2) swap(in1, in2);
		printf("%lld\n", sum(in1, in2, 0, n - 1, 0));
		update(0, n - 1, 0, in3, in4);
	}

	return 0;
}