• 배열 수열 고정
• **구간 [a, b]**에 대한 질문
• 질의가 많을 때 (100, 000 급)
• 배열이 고정일 때
  • 배열 업데이트가 없음 → 조회만

🔖 치트 시트

1. 문제 분류 키워드

• RMQ/구간 쿼리
• 정적 배열 + 질의 많음
• min/max 같은 ‘구간 요약’ 요구

1. 새그먼트 트리 핵심 규칙(중요)

• 트리 배열 크기 → 보통 4N
  • 구간을 반으로 계속 쪼개면 노드 개수는 대략 2 * 2^ceil(log₂N) 정도
  • 관례적으로, 이를 안전하게 커버할 수 있는 정도가 4N 이라고 함
• 노드 인덱스 규칙
  • idx의 왼쪽 자식 → idx * 2
  • idx의 오른쪽 자식 → idx * 2 + 1
• 빌드(전처리)
  • 리프노드 → tree[idx] = arr[pos]
  • 부모 → tree[idx] = merge(tree[idx * 2], tree[idx * 2 + 1])
  • min이면 merge = min, max면 merge = max

1. 쿼리 3가지 케이스

현재 노드 구간 → [L, R] 쿼리 → [a, b]

1. 안 겹침
   • b < L || R < a
   • min: Integer.MAX_VALUE
   • max: Integer.MIN_VALUE
   • 모두 무시되는 값
2. 완전 포함
   • a <= L && R <= b
   • 저장된 값 그대로 반환
3. 부분 겹침
   • 나눈 후 병합 (분할/정복)
   • 왼쪽/오른족 재귀 후 merge