핵심 정리
| 작업 | 비용 | 의미 |
|---|---|---|
| build | O(n) | 전체 배열로 트리 구성 |
| range query | O(log n) | 구간 합, 최솟값, 최댓값 조회 |
| point update | O(log n) | 원소 하나 변경 후 부모 갱신 |
| range update | 별도 lazy 필요 | 구간 전체 변경 |
csharp
int Query(int node, int start, int end, int left, int right)
{
if (right < start || end < left) return 0;
if (left <= start && end <= right) return tree[node];
int mid = (start + end) / 2;
return Query(node * 2, start, mid, left, right)
+ Query(node * 2 + 1, mid + 1, end, left, right);
}구조
Segment tree는 배열 구간을 절반씩 나누어 각 노드가 하나의 구간 값을 들고 있게 만든 트리입니다. 루트는 전체 구간을, 자식은 왼쪽 절반과 오른쪽 절반을 담당합니다.
text
[0..7]
├─ [0..3]
│ ├─ [0..1]
│ └─ [2..3]
└─ [4..7]
├─ [4..5]
└─ [6..7]구간 합 트리라면 각 노드는 담당 구간의 합을 저장합니다. 최솟값 트리라면 각 노드는 담당 구간의 최솟값을 저장합니다. 저장할 값의 결합 연산이 명확해야 트리로 만들 수 있습니다.
배열 크기
구현에서는 보통 tree = new int[n * 4]처럼 넉넉한 배열을 잡습니다. 정확한 크기를 계산할 수도 있지만, 코딩 테스트에서는 4배 배열이 단순하고 안전합니다.
csharp
int Build(int node, int start, int end)
{
if (start == end)
{
tree[node] = arr[start];
return tree[node];
}
int mid = (start + end) / 2;
tree[node] = Build(node * 2, start, mid)
+ Build(node * 2 + 1, mid + 1, end);
return tree[node];
}선택 기준
| 상황 | 선택 |
|---|---|
| 구간 합만 묻고 배열이 바뀌지 않음 | 누적합 |
| 원소 갱신과 구간 질의가 섞임 | Segment tree |
| prefix 기반 합과 point update | Fenwick tree |
| 구간 전체 갱신과 구간 질의 | Lazy segment tree |
| 값 범위가 크지만 실제 좌표가 적음 | 좌표 압축 후 사용 |
Segment tree는 “값이 바뀌는 배열에서 구간 정보를 계속 묻는 문제”에 적합합니다. 정적 배열이라면 누적합이나 sparse table이 더 단순할 수 있습니다.
주의할 점
query에서 세 경우를 명확히 나누어야 합니다. 완전히 벗어난 구간은 항등값을 반환하고, 완전히 포함된 구간은 현재 노드 값을 반환하며, 일부만 겹치면 양쪽 자식을 재귀로 합칩니다.
구간 합의 항등값은 0이지만, 최솟값의 항등값은 매우 큰 값입니다. 저장하는 연산이 바뀌면 query의 기본 반환값도 함께 바뀝니다.
참고 링크
1 sources