세그먼트 트리 (Segment Tree) 개념 정리

• 세그먼트 트리는 구간 합, 최소/최대값 등을 빠르게 구할 수 있는 이진 트리 구조의 자료구조로, O(nlogn)의 공간과 시간을 사용해 만들 수 있다.

• 세그먼트 트리를 만들 때는 재귀적으로 트리의 값을 계산하며 트리를 채워주고, 왼쪽 자식 노드는 인덱스 x2, 오른쪽 자식 노드는 인덱스 x2+1로 접근할 수 있다.

• 세그먼트 트리는 초기화, 구간 합 계산, 갱신 등의 함수를 통해 원하는 구간의 합을 빠르게 구할 수 있는 자료구조입니다.

• 세그먼트 트리는 메모리와 시간의 trade-off를 통해 시간을 단축시키고 싶은 경우에 사용되며, 구간합 또는 구간의 최대 최솟값을 빠르게 계산할 수 있습니다.