정의

세그먼트 트리는 배열을 "구간(segment)"으로 잘게 나눠 각 구간의 합을 노드에 저장한 이진 트리입니다. 루트는 전체 구간, 리프는 원소 하나를 담당합니다.

핵심 특성

• ✓각 노드 = 한 구간 [l, r]의 합. 부모의 합 = 두 자식의 합.
• ✓질의: 구간을 완전히 덮는 노드 몇 개만 골라 합치므로 O(log n).
• ✓점 갱신: 리프부터 루트까지 한 경로의 노드만 다시 합산하므로 O(log n).

시간 복잡도