백준 2042 구간 합 구하기 - C++

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

2042번: 구간 합 구하기

내가 나중에 다시 보려고 쓰는 포스트

 

신촌 알고리즘 캠프 4주차, 세그먼트 트리 연습문제.

 

세그먼트 트리는 연속해서 들어오는 정보들을 트리 형태로 바꾸어, 구간 사이의 정보를 저장해서 

구간 합 구하기 등의 연산을 효율적으로 바꿔주는 트리이다. 

 

<나중에 헷갈리면 내가 다시 볼 블로그 2개>

https://m.blog.naver.com/ndb796/221282210534

41. 세그먼트 트리(Segment Tree)

https://www.acmicpc.net/blog/view/9

세그먼트 트리 (Segment Tree)

 

생각보다 간단한 구현과 논리로, 2진 트리를 입맛에 맞춰 변형한 거에 불과하다.

 

강의에서 듣기로는 세그먼트 트리 자체를 주제로 문제로 내지는 않지만, 중간 중간 활용한다고 하니 잘 알아두자.

 

#include <iostream>

#define MAXNUM 1000001

using namespace std;
using ll = long long;

ll v[MAXNUM];
ll tree[4 * MAXNUM];

long long init(int start, int end, ll node) {
	if (start == end) 
		return tree[node] = v[start];
	int mid = (start + end) / 2;
	return tree[node] = init(start, mid, node * 2) + init(mid + 1, end, node * 2 + 1);
}

void update(int start, int end, ll node, int idx, ll diff) {
	// 범위 넘어가면 갱신 X
	if (idx < start || end < idx) return;
	// 내려가면서 업데이트
	tree[node] += diff;
	// 리프 노드인 경우
	if (start == end) {
		return;
	}
	int mid = (start + end) / 2;
	update(start, mid, node * 2, idx, diff);
	update(mid + 1, end, node * 2 + 1, idx, diff);
}

long long sum(int start, int end, ll 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);
}

int main(void) {

	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	int n, m, k;
	ll a, b, c;

	cin >> n >> m >> k;

	for (int i = 0; i < n; i++) {
		cin >> v[i];
	}

	init(0, n - 1, 1);
	
	for (int i = 0; i < m + k; i++) {
		cin >> a >> b >> c;
		if (a == 1) {
			update(0, n-1, 1, b-1, c - v[b-1]);
			// v 업데이트 안 해주면, 나중에 다시 바꿀 때, 에러
			v[b - 1] = c;
		}
		else {
			cout << sum(0, n-1, 1, b-1, c-1) << "\n";
		}
	}

	return 0;
}