Divide-and-Conquer 기반 O(log n) Range Query 구조 설계

Context

기존 Array 기반 구간 합 계산 시 발생하는 O(n) 시간 복잡도의 성능 병목 현상 분석. Prefix Sum 방식은 쿼리 속도는 빠르나 데이터 수정 시 O(n)의 업데이트 비용이 발생하는 구조적 한계 존재.

Technical Solution

• 임의의 구간 [L, R]을 O(log n)개의 중첩되지 않는 pre-computed 구간으로 분할하는 Segment Tree 구조 채택
• 잎 노드 레이어를 2의 거듭제곱 크기로 설정하여 완전 이진 트리 형태의 인덱싱 체계 구축
• Bottom-up 방식으로 각 노드에 하위 구간의 연산 결과(Sum, Min, Max 등)를 저장하는 계층적 데이터 관리
• Query 수행 시 트리를 상향식으로 탐색하며 구간에 완전히 포함된 노드만 선택적으로 결합하는 최적화 로직 적용
• Point Update 발생 시 해당 리프 노드부터 루트 노드까지의 경로에 있는 조상 노드들만 재계산하는 효율적 갱신 메커니즘 구현
• Iterative 구현 방식을 통한 Recursive 함수 호출 오버헤드 제거 및 메모리 접근 효율성 증대