구간 트리(Segment tree)

구간 트리란

구간의 합을 구하기 위한 트리

 

시간 복잡도

O(logn)

 

트리 만들기

구간 별 합을 저장할 수 있도록 한다.

트리는 완전 이진 트리로 구성되어 있다

자식은 왼쪽 자식은 *2, 오른쪽 자식은 *2+1이다

위 점을 활용하여 각 구간의 합을 부모에 저장한다

 

트리 갱신

해당 Index를 포함하는 구간을 현 Index의 값과의 차이를 합하여 갱신한다

 

특징

1. 배열로 구성

 - 배열의 크기는 보통 N*4 

 - 2^k로 N을 넘을수 있는 최소 수

 

구간 트리의 updata

그 수를 포함한 모든 노드들을 업데이트 시켜준다

 

구간 트리의 탐색

탐색은 4가지 경우가 발생한다

1. 탐색 구간이 겹치지 않는 경우 - 종료

2. 탐색 구간이 정확히 일치하는 경우 - 탐색 완료

3. 탐색 구간이 내부에 포함되는 경우 - 탐색 계속

4. 탐색 구간이 걸쳐 있는 경우 - 계속 탐색

 

0~8

0~4 5~8

0~2 3~4 5~6 7~8

0 1 2 3 4 5 6 7 8

일 경우

2~8검색하면

5~8

3~4

를 검색하면 완료 2를 검색하면 완료

 

시간 복잡도 O(log n)