[자료구조] 백준 12837번: 가계부 (Hard) (C++)

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

12837번: 가계부 (Hard)

처음에 문제의 뜻을 몰라서 TC보고 구간합 세그먼트 트리인 걸 알았다.

그리고 1번 쿼리에서는 b번 인덱스에 C를 더하라는 뜻이다.

이번 문제는 배열 선언이 필요 없다. 애초에 초기 값이 모두 0이기 때문에 따로 선언하지 않고, 바로 트리에다가 코드를 짰다.

초기 값이 0이다 보니 세그먼트 트리 전처리 함수도 필요가 없었다.

[AC 코드]

#include <iostream>
#define ll long long
#define MAX (1000000 + 1)
using namespace std;

ll sgTree[MAX * 4];

void update(int start, int end, int node, int index, ll value) {
	if (index < start || end < index) return;
	sgTree[node] += value;
	if (start == end) return;
	int mid = (start + end) >> 1;
	update(start, mid, node * 2, index, value);
	update(mid + 1, end, node * 2 + 1, index, value);
	return;
}

ll query(int start, int end, int node, int left, int right) {
	if (end < left || start > right) return 0;
	if (left <= start && end <= right) {
		return sgTree[node];
	}
	int mid = (start + end) >> 1;
	return query(start, mid, node * 2, left, right) + query(mid + 1, end, node * 2 + 1, left, right);
}

int n, m;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int a, b; ll c;
		cin >> a >> b >> c;
		if (a == 1) {
			update(1, n, 1, b, c);
		}
		else {
			cout << query(1, n, 1, b, c) << '\n';
		}
	}
	return 0;
}