[백준][2042] 구간 합 구하기

이 포스트는 백준 사이트의 구간 합 구하기 문제 풀이입니다.

문제

해결 과정

이 문제는 세그먼트 트리라는 알고리즘을 사용하면 큰 값이 입력되더라도 빠르게 정답을 구할 수 있습니다.

세그먼트 트리를 사용하지 않고 주어진 명령어에 따라
매번 합을 구하고 숫자를 갱신한다면, 시간초과가 발생합니다.

따라서 임의의 구간별로 합을 미리 계산해 저장하는 세그먼트 트리를 활용하여
구간의 합을 빠르게 확인할 수 있습니다.

기존의 숫자가 새로운 숫자로 변경되면
세그먼트 트리를 순회하면서 값을 변경하면 새로운 숫자로 갱신된
세그먼트 트리를 구할 수 있습니다.

코드 구현

#include <iostream>
#include <vector>

#define ll long long

using namespace std;

vector<ll> numbers;
vector<ll> tree;

void input(int& N, int& M, int& K);
ll init_tree(ll start, ll end, ll node);
void update_number(ll start, ll end, ll node, ll index, ll dif);
ll sum(ll start, ll end, ll node, ll left, ll right);


int main() {
	int N, M, K;
    input(N, M, K);

	init_tree(1, N, 1);

	for(int i = 0; i < M + K; ++i) {
		ll order, a, b;
		cin >> order >> a >> b;
		if(1 == order) {
			update_number(1, N, 1, a, b - numbers[a]);
			numbers[a] = b;
		} else if(2 == order) {
			cout << sum(1, N, 1, a, b) << '\n';
		}
	}

	return 0;
}


void input(int& N, int& M, int& K) {
    ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> N >> M >> K;
	
	numbers.assign(N + 1, 0);
	tree.assign(N * 4 + 1, 0);
	for(int i = 1; i <= N; ++i) {
		cin >> numbers[i];
	}
}

ll init_tree(ll start, ll end, ll node) {
	if(start == end) 
		return tree[node] = numbers[start];
	
	ll mid = (start + end) / 2;

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

void update_number(ll start, ll end, ll node, ll index, ll dif) {
	if(index < start || index > end)
		return;
	
	tree[node] += dif;

	if(start == end)
		return;
	
	ll mid = (start + end) / 2;
	update_number(start, mid, node * 2, index, dif);
	update_number(mid + 1, end, node * 2 + 1, index, dif);
}

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

실행 결과