세그먼트 트리

세그먼트 트리 ?

• 세그먼트 트리는 구간 쿼리 문제를 효율적으로 해결하기 위한 자료구조이다 ! → 특정 범위의 데이터(ex: 구간합, 구간 최소값, 최대값)를 빠르게 계산하고, 데이터가 업데이트될 경우 효율적으로 반영할 수 있다.
• 세그먼트 트리는 완전 이진 트리 형태를 가진다.
• 리프 노드 → 입력 배열의 각 요소를 표현한다.
• 내부 노드 → 특정 범위의 구간 정보를 나타낸다.
• 트리의 루트 노드는 전체 배열의 정보를 나타낸다.

💡 세그먼트 트리 - 구현

• 세그먼트 트리에는 3가지 핵심 연산이 있다.

트리 구성 (Build)

• 입력 배열을 기반으로 세그먼트 트리를 구성한다.
• 각 노드는 특정 범위의 값을 저장한다.

구간 쿼리 (Query)

• 특정 구간 [L, R]의 값을 계산한다.
• 현재 노드의 범위와 [L, R]의 관계에 따라 결과를 반환하거나, 자식 노드로 탐색한다.

업데이트 (Update)

• 배열 값이 변경되었을 때, 해당 값을 세그먼트 트리에 반영한다.
• 변경된 리프 노드부터 부모 노드까지 영향을 주는 노드 값을 갱신한다.

• 시간 복잡도

  • 구성 시간: $O(N)$
  • 쿼리 시간: $O(log N)$
  • 업데이트 시간: $O(log N)$

• 공간 복잡도

  • 세그먼트 트리는 입력 배열 크기의 약 4배의 공간을 사용한다 !