코딩일지

요즘 재밌게 풀고 있는 주제가 세그먼트 트리이다. 아마 다들 이 문제로 처음 세그먼트 트리를 접했을 것이다. 이 문제는 세그먼트 트리를 사용해서 구간의 최솟값을 O(log N)만에 구하는 문제이다. 이처럼 세그먼트 트리는 구간에 대한 질의(Query)를 최적화하는 방법들 중 하나이다. 공부중인 Mo's Algorithm이나 Sqrt Decomposition과 함께 응용되어 사용되기도 하고 여러가지 형태로 변형되어 무궁무진하게 쓰이는 자료구조이다. 이런 이유로 내가 굉장히 재밌어하는 부분이 있다. 세그먼트 트리의 개념은 완전 이진 트리 형태로 구간질의를 최적화 하는 방법으로, 각각의 리프 노드를 길이 1짜리 구간, 그리고 내부 노드는 자식 둘의 구간을 합친 구간에 대한 답으로 구현한다. 예를 들어 수열과 ..