[백준][2042][C++] 구간 합 구하기 (full binary tree)

링크

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

2042번: 구간 합 구하기

해설

사실 이문제는 세그먼트 트리를 이용하거나 펜윅 트리를 이용하면 더욱 빠르게 구할 수 있습니다.

세그먼트 트리를 이용한 방법과 펜윅 트리를 이용한 방법 둘 다 나중에 올리겠습니다.

근데 제가 배우질 않아서 일단 full binary tree 를 이용해서 풀었습니다.

 

코드는 간단합니다.

입력수만큼 받고 2^n 까지 나머지를 0으로 채우고 full binary tree 로 만들면 됩니다.

그 후 각 노드들은 하위 2개노드의 합을 적어두고

만약 값이 바뀔경우 해당 노드와 상위 노드의 갑만 수정해주면 됩니다.

 

a ~ b 까지의 합을 구하는 방법은

1. 쪼개고 쪼개다가 최소 단위가 되었을 경우

2. 쪼개던 중 쪼개진 범위가 구해야 하는 범위 안에 다 들어갈 경우

위의 2가지 경우를 모두 더해주면 a ~ b 까지 합을 구할 수 있습니다.

 

코드

#include <iostream>
using namespace std;
 
int N, M, K, NUM = 1;
long long TABLE[2097152];
 
long long sum(int _l, int _r, int _a, int _b, int _num) {
	if ((_l == _a && _r == _b) || _a == _b)
		return TABLE[_num];
	
	int mid_left = (_a + _b - 1) / 2, list_num_left = _num * 2 + 1;
 
	if (_r <= mid_left)
		return sum(_l, _r, _a, mid_left, list_num_left);
	else if (mid_left < _l)
		return sum(_l, _r, mid_left + 1, _b, list_num_left + 1);
	else
		return sum(_l, mid_left, _a, mid_left, list_num_left) + 
		       sum(mid_left + 1, _r, mid_left + 1, _b, list_num_left + 1);
}
 
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
 
	cin >> N >> M >> K;
 
	int finish, start;
	while (NUM < N) NUM *= 2;
	start = NUM - 1;
	finish = start * 2;
	
	for (int i = start; i < start + N; ++i)
		cin >> TABLE[i];
	
	for (int i = start + N; i <= finish; ++i) {
		TABLE[i] = 0;
	}
 
	for (int i = start - 1; i >= 0; --i) {
		int num = i * 2 + 1;
		TABLE[i] = TABLE[num] + TABLE[num + 1];
	}
 
	for (int i = 0; i < M + K; ++i) {
		int first, second;
		cin >> first >> second;
 
		if (first == 1) {
			long long third;
			cin >> third;
			int number = start + second - 1;
			long long gap = third - TABLE[number];
			while (true) {
				TABLE[number] += gap;
				if (number == 0)
					break;
				number = (number - 1) / 2;
			}
		}
		else {
			int third;
			cin >> third;
			cout << sum(second, third, 1, NUM, 0) << "\n";
		}
	}
 
	return 0;
}