• 주어진 데이터의 구간 합과 데이터 업데이트를 빠르게 수행하기 위해 고안해낸 자료구조의 형태
• 더 큰 범위는 ‘인덱스 트리’라고 불리는데, 코딩 테스트 영역에서는 큰 차이가 없음

핵심 이론

• 세그먼트 트리의 종류
  • 구간 합, 최대 최소 구하기
• 구현 단계
  • 트리 초기화
  • 질의값 구하기(구간 합 또는 최대 최소)
  • 데이터 업데이트

1. 트리 초기화

• 리프 노드의 개수가 데이터의 개수(N) 이상이 되도록 트리 배열을 만듦
• 트리 배열의 크기를 구하는 방법은 2^k ≥ N을 만족하는 k의 최솟값을 구한 후 2^k * 2를 트리 배열의 크기로 정의
• 샘플 데이터
  • {5, 8, 4, 3, 7, 2, 1, 6}
• 리프 노드에 원본 데이터를 입력
• 이때 리프 노드의 시작 위치를 트리 배열의 인덱스로 구해야 하는데, 구하는 방식은 2^k를 시작 인덱스로 취하면 됨
• 2^3 ≥ 8 ⇒ k = 3

• 리프 노드를 제외한 나머지 노드의 값을 채움

• 이렇게 세그먼트 트리를 구성해 놓으면 그 이후 질의와 관련된 결괏값이나 데이터 업데이트 요구 사항에 관해 좀 더 빠른 시간 복잡도 안에서 해결할 수 있음