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

1. 문제

1) 문제 링크

    : www.acmicpc.net/problem/2042

2042번: 구간 합 구하기

 

2) 설명

전형적인 세그멘트 트리 문제다.

인풋에 숫자를 변경하는 인풋과 구간합을 구하는 인풋이 있다.

2. 풀이

1) 알고리즘

    : 세그먼트 트리

 

2) 풀이 설명

 세그먼트 트리를 사용해서 구간합을 구한다.

일반적인 방법은 O(N^2) (이중 반복문)인데 반해 세그먼트 트리를 사용하면 O(logN) 에 구할 수 있어서 시간복잡도를 줄일 수 있다.

풀이는 주석 정도로 설명하고 세그먼트 트리 알고리즘은 따로 포스팅해야겠다.

 

3. 코드

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>

typedef long long LL;

using namespace std;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int segN, N, M, K;
	LL a, b, c;
	cin >> N >> M >> K;
	
	//1. N이상의 2의 제곱수 찾기 -> segN
	for(segN=1;N>segN;segN*=2);

	//2. segmentTree 공간 확보
	vector<LL> segmentTree(segN*2, 0);
	
	//3. 인풋 받기
	for(int i=segN;i<segN+N;i++)
		cin >> segmentTree[i];
	//4. segmentTree 생성
	for(int pat=segN*2-1;pat>1;pat--)
		segmentTree[pat/2] += segmentTree[pat];
	
	//5. 명령어 수행
	for(int i=0;i<M+K;i++){
		cin >> a >> b >> c;
		if(a == 1){
			//5-1. 숫자 변경
			b += segN - 1;
			LL gap = c - segmentTree[b];
			while(b>0){
				segmentTree[b] += gap;
				b /= 2;
			}
		} else if(a == 2) {
			//5-2. 구간합 출력
			b += segN - 1, c += segN - 1;
			LL answer = 0;
			while(b<=c){
				if(b%2 == 1) answer += segmentTree[b++];
				if(c%2 == 0) answer += segmentTree[c--];
				b /= 2;
				c /= 2;
			}
			cout << answer << "\n";
		}
	}

	return 0;
}

 

4. 느낀점

 - 기본 세그먼트도 트리 어렵습니다..  더 공부하겠습니다..