백준 2268 수들의 합

문제링크

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

문제

풀이

기본적인 세그먼트 트리 문제이다.

시행착오

if (bb < cc) cout << sum(tree, 1, 1, n, bb, cc) << '\n';
else cout << sum(tree, 1, 1, n, cc, bb) << '\n';

sum 호출시에 left < right 이어야 하는데 이러한 입력이 주어지는 경우를 간과하고 무작정 sum(tree,1,1,n,bb,cc)로 호출하였다가 한참 해맸다.

코드

#include <iostream>
#include <functional>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;

vector<ll> a(1000010), tree(4000100);
ll sum(vector<ll>& tree, ll node, ll start, ll end, ll left, ll right) {
	if (left > end || right < start) {
		return 0;
	}
	if (left <= start && end <= right) {
		return tree[node];
	}
	return sum(tree, node * 2, start, (start + end) / 2, left, right) + sum(tree, node * 2 + 1, (start + end) / 2 + 1, end, left, right);
}
void update(vector<ll>& tree, ll node, ll start, ll end, ll index, ll diff) {
	if (index < start || index > end) return;
	tree[node] = tree[node] + diff;
	if (start != end) {
		update(tree, node * 2, start, (start + end) / 2, index, diff);
		update(tree, node * 2 + 1, (start + end) / 2 + 1, end, index, diff);
	}
}

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

	
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int aa;
		ll bb, cc;
		cin >> aa >> bb >> cc;

		if (aa) {
			ll diff = (ll)cc - a[bb];
			update(tree, 1, 1, n, bb, diff);
			a[bb] = cc;
		}
		else if (bb < cc) cout << sum(tree, 1, 1, n, bb, cc) << '\n';
		else cout << sum(tree, 1, 1, n, cc, bb) << '\n';
	}
}

후기

생각해보면 이전에도 비슷한 실수를 한적이 있다. 이제 같은 실수는 하지 말자!

세그먼트 트리에 대해 다시한번 공부할 수 있었다.
https://www.acmicpc.net/blog/view/9
위 링크에 세그먼트 트리에 대해 굉장히 자세히 설명이 되어있다.