[자료구조] 백준 2268번: 수들의 합 7 (C++)

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

2268번: 수들의 합 7

구간 합을 구하는 문제라 똑같이 세그먼트 트리로 풀었으나 어느 지점에서 '틀렸습니다'가 계속 떴었다.

문제를 다시 읽어보니 (i > j)와 같은 경우도 sum 함수를 돌리는 것을 알 수 있었다.

즉, i > j인 경우에는 swap을 해주고 나서 sum을 돌려야 한다.

#include <iostream>
#define MAX 1000000 + 1
using namespace std;

long long tree[4 * MAX];
long long arr[MAX];

int n, m, k;

//== Segment Tree INIT == (각 노드에 구간 합)
long long init(int start, int end, int node) {
	if (start == end) {
		return tree[node] = arr[start];
	}
	int mid = (start + end) / 2;
	return tree[node] = init(start, mid, node * 2) + init(mid + 1, end, node * 2 + 1);
}

long long sum(int start, int end, int node, int left, int right) {
	// 범위 밖에 있는 경우
	if (left > end || right < start) return 0;
	// 범위 안에 있는 경우
	if (left <= start && end <= right) return tree[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, long long dif) {
	if (index < start || index > end) return;
	tree[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);
}

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

	cin >> n >> m;

	init(1, n, 1);
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		long long c;
		cin >> c;
		if (a == 1) {
			long long dif = c - arr[b];
			arr[b] = c; // 이 부분은 없어도 된다. 어차피 세그먼트 트리 위주로 돌아가는 문제라서
			// 배열은 따로 업데이트 안 해줘도 됌.
			update(1, n, 1, b, dif);
		}
		else {
			if (b > c) {
				int temp = b;
				b = c;
				c = temp;
			}
			cout << sum(1, n, 1, b, c) << '\n';
		}
	}

	return 0;
}