[백준 1275] 커피숍2 (C++)

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

문제

---

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

어느 날 커피숍의 손님 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³¹보다 크거나 같고, 2³¹-1보다 작거나 같은 정수이다.

 

출력

---

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

 

문제 풀이

---

세그먼트 트리 기본 문제.

 

재귀를 이용해 반씩 나누어 초기화해준다. 범위가 left=right일 때, 즉 리프노드일 때 해당 노드에 배열의 값을 넣어준다. 그 외에는 자식 노드 2개의 합을 더해 저장한다.

특정 노드의 값이 수정되는 경우 역시 재귀를 이용한다. 범위를 반씩 나누어 업데이트를 진행하는데, 범위가 업데이트할 노드를 벗어나면 return한다. 그 외에는 세그먼트 트리의 값이 자식 노드들의 합을 저장하고 있으므로 변경된 값 - 원래 값만큼 더해준다. 만약 리프노드라면 그대로 종료하고 아니라면 범위를 반씩 나누어 업데이트한다. 원래 배열의 값도 변경하는 것을 잊지 않도록 한다.

특정 범위의 합을 구하는 경우 반씩 나누는 재귀를 이용한다. 현재 재귀를 통해 들어온 범위가 구하려는 범위를 벗어난 경우, 합을 구할 때 영향이 미치지 않도록 0을 return한다. 재귀를 통해 들어온 범위가 구하려는 범위인 경우 반씩 나누어 자식 노드들의 합으로 얻어낸다.

 

아래는 코드.

#include <iostream>
using namespace std;
long long* segTree;
long long* arr;

long long init(int left, int right, int nodeNum)
{
	if (left == right)
	{
		return segTree[nodeNum] = arr[left];
	}
	else
	{
		int mid = (left + right) / 2;
		segTree[nodeNum] = init(left, mid, nodeNum * 2) + init(mid + 1, right, nodeNum * 2 + 1);
		return segTree[nodeNum];
	}
}

void update(int left, int right, int nodeNum, int targetNodeNum, long long diff)
{
	if (right < targetNodeNum || left > targetNodeNum)
	{
		return;
	}
	if (left == right)
	{
		segTree[nodeNum] += diff;
		return;
	}
	segTree[nodeNum] += diff;
	int mid = (left + right) / 2;
	update(left, mid, nodeNum * 2, targetNodeNum, diff);
	update(mid + 1, right, nodeNum * 2 + 1, targetNodeNum, diff);
}

long long calc(int left, int right, int start, int end, int nodeNum)
{
	if (right < start || left > end)
	{
		return 0;
	}
	if (left >= start && right <= end)
	{
		return segTree[nodeNum];
	}
	int mid = (left + right) / 2;
	return calc(left, mid, start, end, nodeNum * 2) + calc(mid + 1, right, start, end, nodeNum * 2 + 1);
}

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int N, M;
	int x, y;
	long long a, b;
	cin >> N >> M;
	segTree = new long long[4 * N];
	arr = new long long[N];
	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
	}
	init(0, N - 1, 1);
	for (int i = 0; i < M; i++)
	{
		cin >> x >> y >> a >> b;
		if (x <= y)
		{
			cout<<calc(0, N-1, x-1, y-1, 1)<<"\n";
		}
		else
		{
			cout<<calc(0, N-1, y-1, x-1, 1)<<"\n";
		}
		long long diff = b - arr[a - 1];
		arr[a - 1] = b;
		update(0, N - 1, 1, a - 1, diff);
	}
	return 0;
}