[C++, 세그먼트 트리, 데이터추가 반영] 백준 2042번 구간 합 구하기

www.acmicpc.net/problem/2042

2042번: 구간 합 구하기

21.02.17 데이터 추가 반영하였습니다. 

 

세그먼트 트리의 입문문제라고 할 수 있다.

따라서 세그먼트 트리 초보자에게 구현이 간편한 방법을 소개하고자 한다.

update함수와 query함수 단 2개의 함수만 이용해서 해결할 수 있는 방법이다.

세그먼트 트리 초기화를 update문을 이용해서 구현하면 실행시간은 늘어나지만 구현이 간편해진다는 장점이 있다.

#include <iostream>
using namespace std;

int N, M, K;
long long tree[1<<21];

void update(int node, int s, int e, int idx, long long data)
{
	int m;
	if (s == e)
	{
		tree[node] = data;
		return;
	}
	m = (s + e) / 2;
	if (idx <= m)update(node * 2, s, m, idx, data);
	else update(node * 2 + 1, m + 1, e, idx, data);

	tree[node] = tree[node * 2] + tree[node * 2 + 1];
}

long long query(int node, int s, int e, int qs, int qe)
{
	int m;
	if (e < qs || qe < s) return 0;
	if (qs <= s && e <= qe) return tree[node];

	m = (s + e) / 2;
	return query(node * 2, s, m, qs, qe) 
		+ query(node * 2 + 1, m + 1, e, qs, qe);
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int num;
	long long a, b, c;

	cin >> N >> M >> K;
	for (int i = 1; i <= N; i++){
		cin >> num;
		update(1, 1, N, i, num);
	}
		

	for (int i = 0; i < M + K; i++)
	{
		cin >> a >> b >> c;
		if (a == 1) update(1, 1, N, b, c);
		else cout<<query(1, 1, N, b, c)<<"\n";
	}

	return 0;
}

예제의 경우 트리가 구성되는 것을 그려본다면 아래와 같다.

tree 배열을 크기인 1<<21은 2의 21제곱을 뜻한다. 

약 200만 정도 되는데 이는 최대 입력값인 100만이 모두 끝 노드일 경우를 가정하고 넉넉하게 만들어 주었다.

질문, 오류가 있다면 댓글로 부탁드린다.