[백준] 파이썬 2042 - 구간 합 구하기

 

풀이 . 

세그먼트 트리를 이용하여야 한다.

세그먼트 트리(Segment Tree)란?

세그먼트 트리는 다음 두 연산을 어떻게 더 효율적으로 할 수 있을까라는 고민에서 출발한다.

 1. 구간 l, r(l <= r)이 주어졌을 떄, A[l] + A[l+1] + .... A[r-1] + A[r]을 구해서 출력하기

 2. i번째 수를 v로 바꾸기, A[i] = v

 

2번 연산은 O(1)에 해결할 수 있지만 1번 연산은 l-r의 길이만큼의 시간 즉 O(NM)이 쿼리가 요청될 떄마다 소요된다.

 

세그먼트 트리를 이용하면 1번 연산을 O(logN) 2번 연산도 O(logN)만에 수행이 가능하다.

세그먼트 트리의 리프 노드와 리프 노드가 아닌 다른 노드는 다음과 같은 의미를 지닌다.

 1. 리프 노드: 배열의 수 자체

 2. 다른 노드: 왼쪽 자식과 오른쪽 자식의 합을 저장

즉 어떤 노드의 번호가 a라고 한다면 왼쪽 자식의 번호는 2*a, 오른쪽 자식의 번호는 2*x+1이 된다.

 

우선 세그먼트 트리를 구현하기 위해서는 3단계를 거쳐야 한다.

 1. 트리의 사이즈를 구한 후 DP로 구간합을 전처리

 2. 구간합을 구하는 함수 선언

 3. 원소를 수정하는 함수 선언

 

1. 트리의 형태가 완전 이진트리이므로 트리의 최대로 들어오는 원소의 갯수를 N이라고 한다면

트리의 크기는 최대 2 * 2^ceil(log2(N))이 된다. 

그 후 리프노드에 들어오는 값들을 트리에 넣어주면 된다 리프노드는 인덱스가 트리의 사지으 부터 시작이다.

그 후 사이즈-1의 인덱스들로부터 루트 노드까지는 자식노드들의 합으로 DP를 이용해서 채운다.

 

2. 원하는 구간이 주어질 떄 구간을 찾아서 합을 찾아내야한다.

이분탐색을 이용하여 전체 구간의 시작점과 끝을 mid로 계속 나누어서 찾아간다. 내가 원하는 구간이 포함되어 있으면 반환을 하고 아니라면 넘어간다.

 

3. 원소 업데이트는 리프노드의 값을 바꿔줘야 한다. 리프노드의 값을 바꾸면 연관된 노드들의 값도 변경되어야 한다. 바꾸뀌는 곳의 인덱스(size+변경된 곳 -1)로 기서 그 노드부터 루트 노드까지 올라가 원래의 값과 차이인 값을 모든 노드들에 더한다.

세그먼트 트리를 이용하면 정말 다양한 곳에 사용할 수 있다.

이번에 카카오 블라인드 코딩테스트에서 세그먼트 트리 관련 문제가 나왔는데 풀지 못하여서 세그먼트 트리에대해서 공부를 해보았다.

 

전체 소스코드.