세그먼트 트리

• 배열 구간(interval) 에 대한 정보를 트리 형태로 저장하는 자료구조
• 구간 질의(range query) 를 효율적으로 처리하고 빠른 수정 이 가능
• 매우 유연한 자료구조로, 더 높은 차원으로 쉽게 일반화 가능
  • 2차원 세그먼트 트리는 주어진 행렬의 어떤 부분 직사각형에 대한 합 또는 최솟값 질의를 $O(\log^2 n)$ 시간에 처리할 수 있음
• 메모리는 선형 크기만 필요
  • 크기 $n$ 인 배열을 다루기 위해 $4n$ 개의 노드(정점)만 필요

세그먼트 트리의 가장 단순한 형태

배열 $a[0 \dots n-1]$ 이 주어졌을 때, 세그먼트 트리는 다음을 지원해야 한다.

• 인덱스 $l$ 과 $r$ 사이의 원소 합을 $O(\log n)$ 시간에 구하기
• 배열의 원소 값 변경을 $O(\log n)$ 시간에 처리하기
  • 단순 배열은 원소 갱신은 $O(1)$ 이지만, 각 합 질의를 계산하는 데 $O(n)$ 이 필요함
  • 미리 계산된 누적 합(prefix sum)은 합 질의를 $O(1)$ 에 처리할 수 있지만, 값 변경 시 누적 합을 갱신하는 데 $O(n)$ 이 필요함

세그먼트 트리의 구조

1. 전체 배열에 대한 원소 합을 계산하여 저장
2. 배열을 두 개의 절반으로 나누고, 각 절반의 합을 계산하여 저장
3. 각 구간을 다시 절반으로 분할하며, 모든 구간의 크기가 $1$ 이 될 때까지 반복