구간 트리(Segment Tree)
·
알고리즘
구간 트리(segment tree)는 이미 존재하는 자료들(정렬되지 않음)을 전 처리한 후, 특정 구간에 대한 질의(query)를 효율적으로 답하는 자료구조이다. 물론 작성하려는 부분은 컴퓨터 공학에서 다루는 구간 트리 와는 구현 방식을 비슷하지만 엄밀히 따지면 다른 자료구조로 그저 알고리즘 대회에서 사용되는 구간 트리를 다룰 것이다. 특정 구간에 대한 질의는 그 형식이 다양하다. 예를 들어 특정 구간에 대한 합이 될 수도 있고, 특정 구간에 대한 최솟값 혹은 최댓값이 될 수도 있다. 이를 배열에서 구현하게 되면 특정 구간을 순회하면서 답을 내야 하기 때문에 질문 하나에 대해 O(N)의 시간이 걸리게 된다. 구간 트리는 이진트리로 구현하며, 루트 노드는 모든 구간 [0, n-1]을 의미하고 left는 [..