트리(Tree) | 세그먼트 트리 Segment Tree (알고리즘) 정리

세그먼트 트리 (Segment Tree) | 인덱스 트리 (Index Tree)

세그먼트 트리

• 주어진 데이터들의 (구간 합) (데이터 업데이트) 가 함께 일어나거나, (최대, 최소) 를 구할 때 빠르게 수행하도록 고안해낸 자료구조이다.

→ 더 큰 범위를 ‘인덱스 트리’ 라고 말하기도 한다.

[1] 세그먼트 핵심

1) 데이터 초기화하기

• a) tree 배열 크기 선언
• b) 단말 노드에 arr 원본 배열 초기화
• c) setTree로 단말노드 위의 부모노드들을 자식 노드 활용해 세팅

데이터 초기화 모습

2) 질의값 계산하기 | 구간합, 구간 곱, (구간 안의 최소값, 최대값), 데이터 갱신 등의 질의

• 질의는 보통 여러 가지가 있는데, 구간 합부터 들어보겠다.
• 질의값 계산 시에는 원본 idx를 트리의 idx로 맞춰주는 게 중요하다.

그리고,  getSum에서 각각의 st, ed 에 대해서 구간 합을 구하는 과정은 다음과 같다.

- while(st ≤ ed) 인 동안
- (1) 시작 위치가 (오른쪽 자식 노드일 때) 독립 노드로 선택
- (2) 끝 위치가 (왼쪽 자식 노드일 때) 독립 노드로 선택
- 계속 거슬러 올라가면서 구간에 대한 합/곱/최소,최대 질의 철를 해준다.

getSum 구간 합 구하는 과정