Associativity 기반 Segment Tree 도입으로 Query 시간 복잡도를 O(n)에서 O(log n)으로 단축

Context

배열의 구간 합 또는 최솟값을 구하는 Range Query 수행 시 Brute-force 루프 기반의 O(n) 시간 복잡도로 인한 성능 병목 발생. 빈번한 데이터 업데이트와 쿼리가 동시에 발생하는 환경에서 단순 반복문으로는 실시간 응답성 확보에 한계 노출.

Technical Solution

• Associativity 특성을 활용하여 중첩된 구간의 결과를 미리 계산하고 저장하는 Segment Tree 구조 설계
• 배열을 2의 거듭제곱 크기의 이진 트리 형태로 구성하여 Query 시 필요한 부분 구간만 조합하는 분할 정복(Divide-and-Conquer) 전략 적용
• Leaf 노드부터 Root 노드까지 상향식(Bottom-up)으로 부모 노드를 갱신하는 Update 로직을 통해 데이터 일관성 유지
• 비재귀적(Non-recursive) Flat Array 구현 방식을 통해 함수 호출 오버헤드를 제거하고 인덱스 연산 효율 극대화
• 합계, 최솟값, 최대값, GCD 등 결합 법칙이 성립하는 모든 연산에 범용적으로 적용 가능한 인터페이스 설계