백준 - 구간 합 구하기 (2042) [C++]

이 문제는 세그먼트 트리를 이용해서 풀었다.

 

값을 저장하는 쪽에는 모두 long long 을 써줘야 풀린다.

세그먼트 트리를 구현할 수만 있으면 풀리는 기초 문제였다.

 

몇 가지 주의할 점이 있는데, 첫번째로는 update를 할 때 차이를 더해줘야 하므로 c - arr[b]를 한 값을 update의 인자로 던져줘야 한다. 이 때문에 update 전에 입력 배열인 arr[b] = c를 해줘야 한다. 이거 안해줘서 계속 틀렸었다.

 

두번째는 update의 dif 또한 long long으로 선언해야한다는 것이다. 값이 int 자료형을 가뿐히 뛰어넘을 수 있기 때문이다.

로직은 단순하나 자료형으로 정답률을 낮춘 문제였다.

#include <iostream>
#include <vector>
#include <cmath>
#include <utility>
#include <algorithm>
using namespace std;

#define MAX 1000000

typedef long long LL;

LL segment[MAX * 8 + 1];
LL arr[MAX + 1];
LL N, M, K;

LL init(int start, int end, int node) {
	if (start == end) {
		return segment[node] = arr[start];
	}

	int mid = (start + end) / 2;

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

LL sum(int start, int end, int node, int left, int right) {
	if (left > end || right < start) {
		return 0;
	}

	if (left <= start && end <= right) {
		return segment[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, LL dif) {
	if (index < start || index > end) {
		return;
	}

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

void input() {
	cin >> N >> M >> K;
	for (int i = 1; i <= N; i++) {
		cin >> arr[i];
	}
	init(1, N, 1);
	for (int i = 0; i < M + K; i++) {
		LL a, b, c;
		cin >> a >> b >> c;

		if (a == 1) {
			LL dif = c - arr[b];
			arr[b] = c;
			update(1, N, 1, b, dif);
		} else if (a == 2) {
			cout << sum(1, N, 1, b, c) << '\n';
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	input();

	return 0;
}