세그먼트 트리 (백준 2042번 구간합 구하기)

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

2042번: 구간 합 구하기

 

세그먼트 트리, 구간 합을 구할 때 이진트리를 사용해 빠른 답을 구할 수 있는 자료구조

 

단순히 합을 구할때도 마찬가지 지만 중간에 값이 갱신되거나 구간이 바뀔 때 선형 자료구조보다 빠르게 해답을 구할 수 있다.

 

단순 배열을 사용한 합에서는 덧셈에서만 O(n) 시간이 걸리고 구간이 바뀌면 바뀐만큼 *N 시간이 걸리게 된다.

 

세그먼트 트리의 경우, 이진 트리를 사용하여 임의의 구간을 덧셈할 때 O(logN) 탐색시간이 걸리게 된다. 그 외 시간은 트리의 내용이 바뀌었을 때 log(N)이 걸리며 단순 배열에 비해 빠르다. 

 

 

1. 세그먼트 트리 생성

트리를 생성하기 전에 트리의 크기를 알아야 한다. 

처음에 N개의 숫자가 들어온다면 이 숫자들이 이진트리의 리프노드가 된다.  각 부모 노드들은 자식 노드들의 합을 가진다.

 

 

start : 트리의 시작 요소

end : 트리의 마지막 요소

index : 현재 노드 위치

예시 ) makeTree(1, N, 1) : 

public static long makeTree(int start, int end, int index) {
		if(start == end) {
			tree[index] = num[start];
			return tree[index];
		}
		
		int mid = (start+end) / 2;
		
		tree[index] = makeTree(start, mid, index*2) + makeTree(mid+1, end, index*2+1);
		return tree[index];
	}

 

2. 구간합 구하기

start : 트리의 처음

end : 트리의 마지막

index : 현재 위치

sum_start : 구간합 시작지점

sum_end : 구간 합 마지막 지점

public static long getSum(int start, int end, int index, int sum_start, int sum_end) {
		if(sum_start > end || sum_end < start)
			return 0;
		
		if(sum_start <= start && sum_end >= end)
			return tree[index];
		
		int mid = (start+end)/2;
		
		return getSum(start, mid, index*2, sum_start, sum_end) + getSum(mid+1, end, index*2+1, sum_start, sum_end);
	}

 

 

 

3. 값이 업데이트 되는 경우

next : 업데이트 될 노드

start : 트리의 시작 노드

end : 트리 마지막 노드

index : 갱신할 노드(원소)

update : 갱신 값

 

갱신할 노드는 트리의 노드번호가 아니라 처음 입력받은 숫자 배열의 인덱스다.

update 값은 바꿀 값 - 초기 배열 값 으로 한다. 

 

예시 ) updateTree( 1, 1, N, 5, 10 ) : 처음 입력받은 숫자에서 5번째 숫자를 +10 으로 교체함.(기존 숫자가 1이라면 11으로 교체)

노드번호 1번부터 시작하는 N 크기를 가진 트리를 사용하며 1번 노드부터 업데이트한다.

public static void updateTree(int next, int start, int end, int index, long update) {
		if(index < start || index > end)
			return;
		
		tree[next] += update;
		
		if(start != end) {
			int mid = (start+end)/2;
			
			updateTree(next*2, start, mid, index, update);
			updateTree(next*2+1, mid+1, end, index, update);
		}
	}