트리 - 세그먼트 트리

주어진 데이터의 구간 합과 데이터 업데이트를 빠르게 수행하기 위해 고안해 낸 자료구조 형태가 세그먼트 트리입니다.

 

세그먼트 트리의 핵심 이론

세그먼트 트리의 종류는 구간 합, 최대·최소 구하기로 나눌 수 있습니다.

구현 단계는 트리 초기화하기, 질의값 구하기(구간 합, 최대·최소 구하기), 데이터 업데이트하기로 나눌 수 있습니다.

 

1. 트리 초기화하기

리프 노드의 개수가 데이터의 개수(N) 이상이 되도록 트리 리스트를 만듭니다.

트리 리스트의 크기를 구하는 방법은 2^k >= N을 만족하는 k의 최솟값을 구한 후 2^k * 2를 트리 리스트의 크기로 정의합니다.

 

 

2. 질의값 구하기

3. 데이터 업데이트하기