Segment Tree

🌳 세그먼트 트리(Segment Tree) 정리

---

📌 세그먼트 트리란?

세그먼트 트리(Segment Tree)는 주어진 데이터의 구간 합, 최대/최소, 갱신 등을 빠르게 처리하기 위한 트리 기반의 자료구조
※ 참고: 경우에 따라 인덱스 트리(Index Tree)라고도 불리며, 코딩 테스트에서는 같은 개념으로 봄

---

📚 세그먼트 트리 핵심 이론

✅ 세그먼트 트리의 종류

• 구간 합 트리
• 구간 최대값 트리
• 구간 최소값 트리

✅ 구현 단계

1. 트리 초기화
2. 질의값 구하기 (Query)
3. 데이터 업데이트 (Update)

---

① 트리 초기화

목표: 리프 노드 개수가 주어진 데이터 개수 N 이상이 되도록 트리 배열 구성

트리 크기 계산 공식:

2^k ≥ N 을 만족하는 최소 k를 구한 뒤,
트리 전체 크기는 2^k+1 으로 설정

예시

N = 8
→ 2^3 = 8 (k = 3)
→ 트리 크기 = 2^4 = 16
→ 시작 리프 인덱스 = 8

리프 노드 시작 인덱스: 2^k

---

② 질의값(Query) 구하기

✅ 질의 인덱스 → 트리 인덱스 변환

start_index = 질의 시작 인덱스 + 2^k
end_index   = 질의 끝 인덱스 + 2^k

✅ 질의 연산 절차

1. start_index % 2 == 1 → 노드 선택
2. end_index % 2 == 0 → 노드 선택
3. start_index = (start_index + 1) / 2
4. end_index = (end_index - 1) / 2
5. end_index < start_index → 종료

💡 노드 선택 의미

선택된 노드는 질의 범위에 영향을 주는 독립적 노드이며,
부모 노드를 건너뛰기 위해 (index±1)/2 연산을 수행

✅ 연산 종류별 처리 방식

• 구간 합: 선택된 노드 값을 모두 더함
• 최댓값: 선택된 노드 중 최대값
• 최솟값: 선택된 노드 중 최소값

---

③ 데이터 업데이트

방식: 리프 노드 수정 후 부모 노드로 이동하며 값 갱신

✔️ 트리 종류별 갱신 방식

• 구간 합: 변경 전/후 차이만큼 부모 노드에 더함
• 최대값: 형제 노드와 비교하여 큰 값으로 업데이트 (변경 없으면 종료)
• 최소값: 형제 노드와 비교하여 작은 값으로 업데이트 (변경 없으면 종료)

---

🔁 전체 요약

단계	설명
1. 트리 초기화	2^k ≥ N, 트리 크기 = 2^(k+1)
2. 리프 노드	시작 인덱스 = 2^k
3. 질의 처리	변환 후 연산, start/end 선택 & 이동
4. 업데이트	부모로 이동하며 값 갱신

---

🧠 질의 예시 (구간 합)

질의: arr[3] ~ arr[6] → 트리 인덱스: 11 ~ 14

[1단계]
start_index = 11 → 홀수 → 선택 → 6으로 이동
end_index = 14   → 짝수 → 선택 → 6으로 이동

[2단계]
start_index = 6, end_index = 6 → 선택 후 종료
→ 선택된 노드들 합산 → 구간 합

---

✅ Java에서 트리 크기 빠르게 구하기

// N은 원본 배열 크기
int h = Integer.highestOneBit(N);
if (h < N) h <<= 1;  // 2^k ≥ N 만족
int size = 2 * h;    // 트리 배열 크기

---