세그먼트 트리(Segment tree) - 구간 합 구하기

세그먼트 트리 또는 인덱스 트리

1. 정의

위와같이 각 노드에는 구간에 대한 정보가 저장이 되어있는 트리를 의미한다.

일반적으로 구간의 합 또는 곱, 구간의 최대값 또는 최솟값을 의미합니다.

예)

배열의 데이터 수  :  8개

배열의 데이터 A[8] = {1,2,3,4,5,6,7,8}

목적 : 구간에 대한 합

세그먼트 이론시 높이 3인 트리가 만들어지며 오른쪽 위에 숫자만큼 각 구간에 대한 정보를 담고 있다.

위와 같이 각 노드는 자식에 대한 합을 포함 하고 있다.

배열은 0부터 인덱스가 시작하므로,

A[3] ~ A[6]까지의 합을 구한다고 가정할때, 아래와 같이 주황색 부분의 합만 구하면 된다. 

즉, 4+11+7 = 22로 부분에 대한 합을 쉽게 구할 수 있습니다.

위와같이 수행하면 부분의 합에 대한 부분을

높이가 O(log n)일때, O(log n)만큼의 시간을 들여서 완료할 수 있습니다.

세그먼트 트리에 관한 백준문제

백준 문제 => https://www.acmicpc.net/problem/2042  (  구간 합 구하기 )

참고한 사이트

http://isukorea.com/blog/home/waylight3/216

추가개념

만약에 구간에 대한 값을 증가시키거나 감소시킬 때는 아래의 개념을 사용하면 됩니다.

+) Lazy propagation

https://www.acmicpc.net/blog/view/26

http://bowbowbow.tistory.com/4

백준 문제 => https://www.acmicpc.net/problem/10999 ( 구간 합 구하기2 )