주어진 데이터의 구간 합과
데이터 업데이트를 빠르게 수행
구간 합 OR 최대, 최소 구하기에 사용
1. 트리 초기화하기
리프 노드의 개수가 데이터 개수(N) 이상이 되도록
트리 배열을 만든다.
2^k >= N을 만족하는 k의 최솟값을 구하고
2^k * 2를 트리 배열의 크기로 정의
예를 들어
N = 8이면 k = 3
배열 크기를 16으로 정한다.
샘플 데이터
{5, 8, 4, 3, 7, 2, 1, 6}
2. 질의값 구하기
주어진 질의 인덱스를
세그먼트 트리의 리프 노드에 해당하는 인덱스로 변경
세그먼트 트리 index = 주어진 질의 index + 2^k - 1
질의에서의 시작 인덱스와 종료 인덱스에 대해
부모 노드로 이동하면서 주어진 질의에 해당하는 값을 구함
1. start_index % 2 == 1
해당 노드 선택
2. end_index % 2 == 0
해당 노드 선택
3. start_index depth 변경
start_index = (start_index + 1) / 2
4. end_index depth 변경
end_index = (end_index - 1) / 2
5. end_index < start_index가 되면 종료
1~2에서 해당 노드를 선택하는 것은
해당 노드의 부모가 나타내는 범위가 질의 범위를 넘어가
해당 노드를 질의값에 영향을 미치는 독립 노드로 선택
해당 노드의 부모 노드는 대상 범위에서 제외
해당 범위에 해당하는 부모 노드로 이동하기 위해!
(start_index + 1) / 2, (end_index - 1) / 2를 하는 것.
질의에 해당하는 노드 선택 방법
1. 구간 합
선택된 노드를 모두 더함
2. 최댓값 구하기
선택된 노드 중 MAX 값 선택
3. 최솟값 구하기
선택된 노드 중 min값 선택
3. 데이터 업데이트하기
데이터 바꾸고 올라가면서 확인하면 됨.
업데이트가 일어나지 않으면 종료
부모 노드로 이동하기
index = index / 2
