Segment Tree1 [Algorithm] Segment Tree (구간 트리) Segment Tree (구간 트리) 구간 트리는 배열의 특정 구간에 대한 질의를 빠르게하기 위해 사용할 수 있다. 예를 들어 어떤 구간의 최소치를 구하고 싶다고 해보자. 보통 사용하는 방법은 구간 내 숫자를 하나하나 확인하면서 최소치를 찾는 것으로, O(N)의 시간이 걸린다. 이때 배열을 전처리해 구간 트리를 사용하면 O(N log N)의 시간에 찾을 수 있다. 구간 트리는 '주어진 배열의 구간들을 표현'하는 이진 트리를 만든다. 루트는 배열의 전체구간을 표현하고, 한 트리의 왼쪽 자식과 오른쪽 자식은 해당 구간의 왼쪽 반과 오른쪽 반을 표현한다. 각 노드는 해당 구간에 대한 계산 결과를 저장해둔다. 이렇게 전처리해둔 트리가 있다면 어떤 구간 [i, j]가 주어지면 이 구간을 구간 트리의 노드에 포함된.. 2023. 3. 23. 이전 1 다음
