Segment Tree

특징

Segment Tree는 구간 혹은 범위에 대한 빠른 Query를 처리하기 위해 사용하는 자료구조이며, 구간 정보를 이진 트리 구조로 저장합니다. 이를 통해, 구간 합이나 최솟값(최댓값) 등을 $log_n$ 시간에 계산할 수 있습니다.어떻게 사용하는지에 대한 이해를 돕기 위해 백준 10868번_최솟값 문제를 예시로 그림을 통해 살펴보겠습니다.

우선, 해당 문제는 주어지는 구간에 대하여 최솟값을 찾아내는 문제입니다. 다음 사진과 같은 입력이 들어온다고 가정해 보겠습니다.

위 그림에서 1~10 사이에 있는 최솟값을 찾으면 5, 3~5 사이에 있는 최솟값을 찾으면 38임을 알 수 있습니다. 이러한 연산을 수행하는 경우 상관없지만, 계속해서 수행이 필요한 경우 이는 상당한 시간이 소요됩니다. 이를 더욱 효율적으로 수행하기 위해 Segment Tree를 사용하여 다음과 같이 나타낼 수 있습니다.

구현

Segment Tree 클래스 정의

다음 코드와 같이 Segment Tree 클래스를 정의했습니다.

Segment Tree 초기화

다음 코드와 같이 Segment Tree 초기화를 진행했습니다.

각 구간에 해당하는 최솟값 찾기

다음 코드를 사용해 각 구간에 해당하는 최솟값을 찾았습니다.

추가 문제

백준 2042_구간 합 구하기