Quick Reference
| 작업 | 비용 | 의미 |
|---|---|---|
| build | O(n) | 전체 배열로 트리 구성 |
| range query | O(log n) | 구간 합, 최솟값, 최댓값 조회 |
| point update | O(log n) | 원소 하나 변경 후 부모 갱신 |
| range update | 별도 lazy 필요 | 구간 전체 변경 |
var tree = new RangeSumTree(values);
tree.Set(index: 3, value: 10);
long sum = tree.Query(left: 1, right: 4); // 양 끝 포함배열이 바뀌지 않으면 누적합이 더 단순합니다. 원소 갱신과 구간 질의가 섞일 때만 segment tree의 O(log n) 비용을 감수합니다.
구조
Segment tree는 배열 구간을 절반씩 나누어 각 노드가 하나의 구간 값을 들고 있게 만든 트리입니다. 루트는 전체 구간을, 자식은 왼쪽 절반과 오른쪽 절반을 담당합니다.
[0..7]
├─ [0..3]
│ ├─ [0..1]
│ └─ [2..3]
└─ [4..7]
├─ [4..5]
└─ [6..7]구간 합 트리라면 각 노드는 담당 구간의 합을 저장합니다. 최솟값 트리라면 각 노드는 담당 구간의 최솟값을 저장합니다. 저장할 값의 결합 연산이 명확해야 트리로 만들 수 있습니다.
합 트리 구현
구현에서는 보통 tree = new long[n * 4]처럼 넉넉한 배열을 잡습니다. 정확한 크기를 계산할 수도 있지만, 코딩 테스트에서는 4배 배열이 단순하고 안전합니다. 아래 구현은 빈 배열도 만들 수 있지만, 원소가 없는 구간은 조회·갱신하지 않는 계약입니다.
sealed class RangeSumTree
{
private readonly long[] tree;
private readonly int length;
public RangeSumTree(IReadOnlyList<int> values)
{
length = values.Count;
tree = length == 0 ? Array.Empty<long>() : new long[length * 4];
if (length > 0) Build(node: 1, start: 0, end: length - 1, values: values);
}
public long Query(int left, int right)
{
if (left < 0 || right < left || right >= length)
{
throw new ArgumentOutOfRangeException();
}
return Query(node: 1, start: 0, end: length - 1, left: left, right: right);
}
public void Set(int index, int value)
{
if ((uint)index >= (uint)length) throw new ArgumentOutOfRangeException(nameof(index));
Set(node: 1, start: 0, end: length - 1, index: index, value: value);
}
private long Build(int node, int start, int end, IReadOnlyList<int> values)
{
if (start == end) return tree[node] = values[start];
int middle = start + (end - start) / 2;
return tree[node] = Build(node * 2, start, middle, values)
+ Build(node * 2 + 1, middle + 1, end, values);
}
private long Query(int node, int start, int end, int left, int right)
{
if (left <= start && end <= right) return tree[node];
int middle = start + (end - start) / 2;
long sum = 0;
if (left <= middle) sum += Query(node * 2, start, middle, left, right);
if (right > middle) sum += Query(node * 2 + 1, middle + 1, end, left, right);
return sum;
}
private void Set(int node, int start, int end, int index, int value)
{
if (start == end)
{
tree[node] = value;
return;
}
int middle = start + (end - start) / 2;
if (index <= middle) Set(node * 2, start, middle, index, value);
else Set(node * 2 + 1, middle + 1, end, index, value);
tree[node] = tree[node * 2] + tree[node * 2 + 1];
}
}합이 int를 넘을 수 있으면 저장 배열과 반환값을 long으로 둡니다. 최솟값이나 최댓값으로 바꾸려면 +와 0뿐 아니라 Math.Min·매우 큰 항등값 또는 Math.Max·매우 작은 항등값까지 한 쌍으로 바꿔야 합니다.
선택 기준
| 상황 | 선택 |
|---|---|
| 구간 합만 묻고 배열이 바뀌지 않음 | 누적합 |
| 원소 갱신과 구간 질의가 섞임 | Segment tree |
| prefix 기반 합과 point update | Fenwick tree |
| 구간 전체 갱신과 구간 질의 | Lazy segment tree |
| 값 범위가 크지만 실제 좌표가 적음 | 좌표 압축 후 사용 |
Segment tree는 “값이 바뀌는 배열에서 구간 정보를 계속 묻는 문제”에 적합합니다. 정적 배열이라면 누적합이나 sparse table이 더 단순할 수 있습니다.
주의할 점
query에서 세 경우를 명확히 나누어야 합니다. 완전히 벗어난 구간은 항등값을 반환하고, 완전히 포함된 구간은 현재 노드 값을 반환하며, 일부만 겹치면 양쪽 자식을 재귀로 합칩니다.
구간 합의 항등값은 0이지만, 최솟값의 항등값은 매우 큰 값입니다. 저장하는 연산이 바뀌면 query의 기본 반환값도 함께 바뀝니다.
참고 링크
1 sources