세그먼트 트리
주어진 데이터의 구간 합, 데이터 업데이트를 빠르게 하기 위해 고안
- 구간 합 구하기
- 최대, 최소 구하기
과정
- 토리 초기화 하기
1. 리프 노드의 개수가 데이터의 개수(n) 이상이 되도록 트리 리스트 만들기
(2**k) >= n 을 만족하는 k의 최소값을 구한 후
(2**k) * 2 를 트리 리스트의 크기로 정의
2. 리프 노드에 원본 데이터 입력하기
리프 노드의 시작 위치를 트리 리스트의 인덱스로 구함
((2**k)를 시작 인덱스로 취함)
3. 1 ~ (2**k)-1 구간 채우기 (by. 질의)
> 구간 합: A[n] = A[2n] + A[2n+1]
> 최대: A[n] = max(A[2n], A[2n+1])
> 최소: A[n] = min(A[2n], A[2n+1])
의 방식으로 앞 리스트 채우기
- 질의 값 구하기 (구간합 or 최대최소)
주어진 질의 인덱스를 세그먼트 트리의 리프 노드에 해당하는 인덱스로 변경
(기존 sample 기준 인덱스 != 세그먼트 트리 인덱스 -> 인덱스 변경이 필요함!)
1. 질의 인덱스를 세그먼트 트리 인덱스로 변경하는 방법
세그먼트 트리 인덱스 = 주어진 길이 index + (2 ** k) - 1
2. 질의 구하는 과정
> start_index % 2 == 1 일 때 해당 노드 선택
> end_index % 2 == 1일 때 해당 노드 선택
> start_index depth 변경: start_index = (start_index + 1) / 2 연산 실행
> end_index depth 변경: end_index = ( end_index - 1) / 2 연산 실행
3. 1~2 반복하다가 end_index < start_index 시 종료
