Segment Tree

구간 사이의 정보를 저장하는 Data Structure

Problem

아래의 문제를 생각해 보자.

size가 n인 array가 있을 때, 두 가지 operation을 생각할 수 있다.
1. Range Sum query: l부터 r까지 값들의 합 ( 0 <= l <= r <= n - 1 )
2. Update: array[i]의 값을 변경하기

Solutions

다음과 같은 세 가지 해결 방법을 떠올릴 수 있다.
1) Brute Force
2) Sum Array
3) Segment Tree

1) Brute Force

• Query: Naive하게 l 부터 r까지 더한다. 시간 복잡도는 O(n)이다.
• Update: array[i] 값 하나를 바꾼다. 시간 복잡도는 O(1)이다.

update는 얼마든지 들어와도 빠르게 처리하지만, query가 많다면 적합하지 않은 방법이다.

2) Sum Array

0~i 까지의 합을 미리 계산하여, sumArray[i]에 저장한다.

• Query: sumArray를 활용하면 구할 수 있다. O(1)이 걸린다.
• Update: array[i] 값을 변경할 때, sumArray[i...n]을 수정해야 한다. O(n)

query에는 빠르게 대응할 수 있지만, update 요청이 많으면 적합하지 않다.

3) Segment Tree

반면에 Segment Tree는 O(1)보다는 느리지만, 모든 상황에서 시간 복잡도가 O( logn )이다.

ST의 특성은 다음과 같다.

• 색칠된 leaf nodes가 array의 elements이다.
• 나머지는 자식 노드의 합을 저장한다.
• [ ]는 구간을 나타낸다.
  

필요 nodes 개수

elements가 n개, 그 사이에 n-1개가 있으므로, 총 2n-1개 이다.
(이는 dummy를 제외한 크기이다. )

ST의 크기

그림을 보며 계산해보면,
height = ceil( log2(n) ) 이다.
따라서, size = 2^(height+1) - 1 인 array를 사용하여 ST를 생성해야 한다.
(이는 dummy를 포함한 크기이다.)
(size 계산 시, double 형인 pow를 쓰기보다는, ( 1 << (h + 1) ) - 1 와 같이 직접 계산하는 게 좋다. 이때, 괄호로 정확히 연산 순서를 명확히 해줄 필요가 있다.)

정리

위의 특성을 기반으로, 아래와 같이 구현할 수 있다.

• Construction: recursive call을 통해 구현, O( n )
• Query: recursive call을 통해 검색, O( logn )
• Update: recursive call로 update, O( logn )

EXAMPLES

Segment Tree를 적용하는 대표적인 문제들은 다음과 같다.
1. Sum of given range
2. Range minimum query
3. Product of given range
..

심화

• Lazy Propagation in Segment Tree
• Persistent Segment Tree
• Fenwick Tree