boj,백준) 2042. 구간 합 구하기( C / C++)

1. 문제 링크

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

2042번: 구간 합 구하기

2. 문제 개요

 숫자가 N개 주어져있다. 그 중간 일정 구간의 합을 구하려고 한다. 수가 변경될 때도 있다.

 

3. 문제 힌트

세그먼트 트리 자료구조를 알아야한다.

부분합을 배열로 빨리 구할 수는 있다.

예를 들면 5~10까지의 부분합은 (1~10까지의 부분합) - (1~5까지의 부분합)으로 구할 수 있다.

하지만 이경우는 원본 데이터가 수정되고 다시 부분합을 계산하는데 O(n)의 시간 복잡도가 걸리므로 O(n^2)가 되고 시간 초과가 된다.

4. 문제 풀이

이 문제를 보러 오시는 분들은 세그먼트 트리 자료구조의 기본은 알고 있다고 가정하고 풀이를 하면,

 

(1) 원본 데이터 -> 세그먼트 트리로 초기화

(2) 부분합 찾기

(3) 데이터 업데이트 하기

크게 3가지로 나눌 수 있다.

 

이 부분은 코드로 보는 것이 더 이해가 잘될 거라 생각됩니다.

 

이 문제의 핵심은 O(N^2)를 Segment tree를 사용하여 O(NlogM)으로 (M: 값 변경 명령의 수) 만드는 것이 핵심

 

5. 코드

#include <cstdio>
#include <algorithm>
#include <cmath>	//log, ceil
#include <vector>
using namespace std;

int n, m, k;
vector<long long int> arr;

class SGT {

public:
	SGT(){}
	SGT(long long int tree_size) { tree.resize(tree_size); }
	long long int init_tree(int node, int start, int end)
	{
		if (start == end)
			return tree[node] = arr[start];
		int mid = (start + end) / 2;
		return tree[node] = init_tree(2 * node, start, mid) + init_tree(2 * node + 1, mid + 1, end);
	}

	long long int sum_tree(int node, int start, int end, int left, int right)
	{
		//start end는 node의 coverage
		if (right < start || end < left)	
			return 0;
		if (left <= start && end <= right)
			return tree[node];

		int mid = (start + end) / 2;

		return sum_tree(2 * node, start, mid, left, right) + sum_tree(2 * node + 1, mid + 1, end, left, right);

	}
	void update_tree(int node, int start, int end, int index, long long int diff)
	{
		if (index < start || end < index)
			return;
		tree[node] += diff;
		if (start != end)
		{
			int mid = (start + end) / 2;
			update_tree(2 * node, start, mid, index, diff);
			update_tree(2 * node + 1, mid + 1, end, index, diff);
		}
		return;
	}
	vector<long long int> tree;
};

int main()
{
	scanf("%d %d %d", &n, &m, &k);
	arr.resize(n);	//for 1~n
	for (int i = 0; i < n; ++i)
		scanf("%d", &arr[i]);

	int h = (int)ceil(log2(n));
	int tree_size = 1 << (h + 1);
	
	SGT	sgt_tree(tree_size);
	//convert array to tree
	sgt_tree.init_tree(1, 0, n - 1);

	for (int i = 0; i < m + k; ++i)
	{
		int type, b, c;
		scanf("%d %d %d", &type, &b, &c);

		
		if (type == 1)
		{
			//update
			int diff = c - arr[b - 1];
			arr[b - 1] = c;
			sgt_tree.update_tree(1, 0, n - 1, b - 1, diff);	//array에서 b-1번 인덱스
		}
		else
		{
			//print the sum
			printf("%lld\n",sgt_tree.sum_tree(1, 0, n - 1, b - 1, c - 1));
		}
	}
	
	return 0;
}

6. 결과 사진

지적, 댓글 언제나 환영입니다~