세그먼트 트리(Segment Tree) 자료구조

세그먼트 트리(Segment Tree) 자료구조

주어진 데이터의 질의값 구하기(구간 합, 최대・최소)나 데이터 업데이트를 빠른 시간 복잡도 안에서 수행하기 위해 고안해 낸 자료구조

 

* 더 큰 범위는 '인덱스 트리'라고 불린다.

 

 

세그먼트 트리 종류

• 구간 합

A[N] = A[2N] + A[2N + 1]

[ 구간 합 세그먼트 트리 예시 ]

 

• 최대

A[N] = max(A[2N], A[2N + 1])

[ 최대 세그먼트 트리 예시 ]

 

• 최소

A[N] = min(A[2N], A[2N + 1])

[ 최소 세그먼트 트리 예시 ]

 

 

세그먼트 트리 핵심 이론

• 트리 배열의 크기

2ᵏ ≥ N을 만족하는 k의 최솟값을 구한 후 2ᵏ * 2를 트리 배열의 크기로 정의 (N : 데이터의 개수)

 

[ 예시 ]

N = 8의 경우, 2³ ≥ 8

⇒ 배열의 크기 : 2³ * 2 = 16

 

• 시작 인덱스 : 2ᵏ

 

[ 예시 ]

k = 3의 경우

시작 인덱스 : 2³ = 8

[ 세그먼트 트리 예시 ]

 

 

 

 

 

* <Do It! 알고리즘 코딩테스트 with C++편>을 참고하였습니다.