"이 구간 합, 빨리 알려줘"
배열 [5, 8, 6, 3, 2, 7, 2, 6]이 있다고 합시다. 누군가 묻습니다. "2번부터 5번까지 다 더하면 얼마야?" (6+3+2+7 = 18)
한 번이면 그냥 더하면 됩니다. 그런데 이런 질문이 수십만 번 들어오고, 중간중간 값도 바뀐다면? 매번 구간을 처음부터 더하면 질의 하나에 O(n) — 금세 시간 초과입니다.
예: 구간 합
query(2, 5)→ 18. 그러다arr[4]를 2에서 10으로 바꾸면, 다시query(2, 5)→6+3+10+7 = 26.
누적합이면 안 될까? (절반만 맞는 답)
"미리 다 더해두자"는 발상이 누적합(prefix sum) 입니다. prefix[i]에 0..i까지의 합을 저장해두면, 구간 합은 prefix[r] - prefix[l-1]로 O(1) 에 끝나죠.
질의만 보면 완벽합니다. 문제는 갱신입니다. arr[4] 하나만 바꿔도, 그 뒤의 prefix[4], prefix[5], ...가 전부 틀어집니다. 갱신 한 번에 O(n) 을 다시 쓰는 셈이죠.
- •누적합: 질의 O(1) / 갱신 O(n) ← 자주 바뀌면 치명적
- •우리가 원하는 것: 질의도, 갱신도 둘 다 빠르게
왜 트리로 묶을까? — "구간을 미리 합쳐 둔다"
여기서 발상을 바꿉니다. 배열을 구간(segment) 단위로 잘게 쪼개 각 구간의 합을 미리 노드에 적어두는 겁니다.
- •리프: 원소 하나(
[4-4]) - •내부 노드: 두 자식 구간을 합친 구간(
[4-5],[4-7]…) - •루트: 전체(
[0-7])
그러면 신기한 일이 벌어집니다. [2-5]의 합을 구할 때, 딱 두 노드 [2-3](합 9)과 [4-5](합 9)만 골라 더하면 18이 나옵니다. 원소 4개를 일일이 더한 게 아니라, 미리 합쳐둔 덩어리 2개를 합친 거예요.
핵심은 부모의 합 = 두 자식의 합이라는 규칙입니다. 덕분에 어떤 구간이든 O(log n)개의 노드 조각으로 덮을 수 있습니다.
갱신도 한 줄기만 고치면 끝
값이 바뀌면 어떻게 할까요? arr[4]를 10으로 바꾼다면:
1. [4-4] 리프를 10으로
2. 그 부모 [4-5]를 다시 합산 (9 → 17)
3. 또 그 부모 [4-7] (17 → 25)
4. 루트 [0-7] (39 → 47)
리프에서 루트까지 딱 한 줄기(path) 의 노드만 다시 더하면 됩니다. 트리 높이가 log n이니, 갱신도 O(log n). 누적합의 O(n) 갱신과 비교하면 차원이 다르죠.
균형이 핵심입니다. 세그먼트 트리는 질의도 O(log n), 갱신도 O(log n)으로 *둘 다* 빠릅니다. 값이 계속 바뀌는 상황에서 빛을 발합니다.
직접 눈으로 확인하기
리프부터 루트까지 트리가 차곡차곡 쌓이고, 질의가 구간을 따라 내려가며 겹치는 노드만 골라 합치고, 갱신이 리프에서 루트까지 한 줄기를 타고 올라가며 합을 고치는 전 과정을 단계별 시각화로 준비했습니다. 각 노드가 담당하는 구간과 합이 한눈에 보입니다.