백준 2042번 구간 합 구하기

< 백준 2042번 구간 합 구하기 - 마포 코딩박 >

사용한 알고리즘: 세그트리


 구간합을 구하는 문제였습니다. 저는 세그트리를 써서 해결하였습니다.
 ( Fenwick tree 나 기타 다른 방법으로도 구현이 가능합니다. )

문제풀이는 다음과 같습니다.
(1) (코드 4, 7)
 N 이 최대 10^6 입니다.
 Segtree 크기는 2 제곱으로 잡아줘야 합니다. ( node가 8개일때 생각하면 편합니다. )
 2^20>10^6 이므로 노드개수가 2^20 개라 생각했습니다.
 노드들을 쌓아올릴 2^20개가 추가로 필요하여 총 2*2^20 으로 배열 크기를 잡았습니다.

(2) (코드 22~30)
 세그트리를 업데이트 (구성) 하는 코드입니다.
 해당 index 를 바꿀 숫자로 바꾼 후 위에 쌓아올린 칸을 바꿔줍니다.

(3) (코드 8~20)
 구간합을 구하는 코드입니다.
 Segtree 의 Root 인 index=1 인 지점부터 차례로 보며 원하는 구간에 쏙 들어오는 index칸의 값을 구해줍니다.

 세그트리가 한번에 생각이 어려우신 분들은 8개의 노드들을 쌓아올리는걸 그려보시면 편합니다. ( 저도 항상 8개 가지고 생각을 합니다. )

	#include <iostream>
	using namespace std;
	typedef long long ll;
	const ll MAX = 1<<20;
	int N, M, K;
	ll arr[2*MAX];
	// 구간합 구하기
	// 현재 index , index가 갖고있는 시작점, 끝점, 구하고자하는 구간의 시작점, 끝점
	ll Sum(int idx, int NowS, int NowE, int WanS, int WanE){
	// 원하는 범위 나가리
	if(NowS>WanE || NowE<WanS) return 0LL;
	// 기저 도달 (노드 한개)
	if(idx>=MAX) return arr[idx];
	// 원하는 범위에 쏙 들어옴
	if(NowS>=WanS && NowE<=WanE) return arr[idx];
	// 쪼개
	int mid = (NowS+NowE)/2;
	return Sum(2*idx, NowS, mid, WanS, WanE) + Sum(2*idx+1, mid+1, NowE, WanS, WanE);
	}
	// 세그트리 업데이트
	// 해당 index , 바뀌는 숫자
	void update(int idx, int num){
	// 해당숫자 변경
	arr[idx] = num;
	// 해당숫자 위로 변경
	while(idx>1){
	idx/=2;
	arr[idx] = arr[2*idx]+arr[2*idx+1];
	}
	}
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> N >> M >> K;
	for (int i = 0; i < N; ++i){
	int a;
	cin >> a;
	// 받을때마다 업데이트, 기저는 MAX+0 ~ MAX+(N-1) 까지입니다.
	update(MAX+i, a);
	}
	for(int i = 0; i < M+K; ++i){
	int a, b, c;
	cin >> a >> b >> c;
	if(a==1)
	update(MAX+(b-1), c);
	else
	cout << Sum(1,1,MAX,b,c) << '\n';
	}
	return 0;
	}

view raw BOJ 2042.cpp hosted with ❤ by GitHub