DAMPER's 낙서장

PS분야에서 정말 다양하게 쓰이고 있는 자료구조로 자유자재로 쓰고싶은 마음에 이번 기회에 정리하고자 한다. 세그먼트 트리는 흔히 일차원 배열의 특정 구간에 대한 쿼리를 빠르게 답하는 데 사용한다. 물론 다차원 배열의 특정 구간에 대한 세그먼트 트리도 구현이 가능하다. 가장 기본적인 예로 어떤 배열의 부분 구간의 최소치를 구하는 연산을 여러번 하는 것이다. 배열 A = {1, 2, 1, 4, 6, 1, 5, 8}가 있다면 구간[2, 4]의 최소값은 1이고 구간[6, 7]의 최소값은 5이다. 이 문제를 세그먼트 트리를 통해 O(qlogn)에 해결할 수 있다. 세그먼트 트리의 기본적인 아이디어는 주어진 배열의 구간들을 표현하는 이진 트리를 만드는 것이다. 루트는 전체 구간을 표현하고, 리프는 1개만을 표현한다..