세그먼트 트리 — 구간 합을 O(log n)에 구하는 법
배열에서 구간 합을 구하는 것은 O(n)인데, 값이 자주 바뀌는 상황에서도 빠르게 구간 합을 구할 수 있을까요?
세그먼트 트리란
세그먼트 트리(Segment Tree)는 배열의 구간 정보를 트리로 관리 하는 자료구조입니다.
- 구간 합, 구간 최솟값/최댓값 등의 쿼리를 O(log n) 에 처리합니다.
- 원소 값 변경(업데이트)도 O(log n) 에 반영합니다.
왜 필요한가
| 방법 | 구간 합 쿼리 | 값 업데이트 |
|---|---|---|
| 단순 배열 | O(n) | O(1) |
| 누적 합 배열 | O(1) | O(n) |
| 세그먼트 트리 | O(log n) | O(log n) |
쿼리와 업데이트가 모두 빈번한 상황에서 세그먼트 트리가 최적입니다.
구조 이해
배열 [1, 3, 5, 7, 9, 11]에 대한 세그먼트 트리:
[36] ← 전체 합 (0~5)
/ \
[9] [27] ← 절반씩 나눔
/ \ / \
[4] [5] [16] [11]
/ \ / \
[1] [3] [7] [9]
0 1 2 3 4 5 ← 원본 배열 인덱스
- 리프 노드: 원본 배열의 각 원소
- 내부 노드: 자식들의 구간 합 (또는 최솟값/최댓값 등)
- 루트 노드: 전체 구간의 합
구현 — 배열 기반
세그먼트 트리는 배열로 구현합니다. 노드 i의 자식은 2*i와 2*i+1입니다.
public class SegmentTree {
private int[] tree;
private int n;
public SegmentTree(int[] arr) {
n = arr.length;
tree = new int[4 * n]; // 충분한 크기 할당
build(arr, 1, 0, n - 1);
}
// 트리 구축: O(n)
private void build(int[] arr, int node, int start, int end) {
if (start == end) {
tree[node] = arr[start]; // 리프 노드
} else {
int mid = (start + end) / 2;
build(arr, 2 * node, start, mid); // 왼쪽 자식
build(arr, 2 * node + 1, mid + 1, end); // 오른쪽 자식
tree[node] = tree[2 * node] + tree[2 * node + 1]; // 합산
}
}
}
구간 합 쿼리
배열의 [l, r] 구간의 합을 구합니다.
// 구간 [l, r]의 합을 구함: O(log n)
public int query(int l, int r) {
return query(1, 0, n - 1, l, r);
}
private int query(int node, int start, int end, int l, int r) {
// 현재 구간이 쿼리 범위 밖
if (r < start || end < l) {
return 0;
}
// 현재 구간이 쿼리 범위에 완전히 포함
if (l <= start && end <= r) {
return tree[node];
}
// 부분적으로 겹침 → 자식에게 위임
int mid = (start + end) / 2;
int leftSum = query(2 * node, start, mid, l, r);
int rightSum = query(2 * node + 1, mid + 1, end, l, r);
return leftSum + rightSum;
}
쿼리 동작 예시
배열 [1, 3, 5, 7, 9, 11]에서 query(1, 4) (인덱스 1~4의 합):
[36] (0~5)
/ \
[9] (0~2) [27] (3~5)
/ \ / \
[4] [5] [16] [11]
(0~1) (2~2) (3~4) (5~5)
- 루트(0~5): 부분 겹침 → 자식 탐색
- 왼쪽(0~2): 부분 겹침 → 자식 탐색
- (0~1): 부분 겹침 → 자식 탐색
- (0~0): 범위 밖 → 0 반환
- (1~1): 완전 포함 → 3 반환
- (2~2): 완전 포함 → 5 반환
- 오른쪽(3~5): 부분 겹침 → 자식 탐색
- (3~4): 완전 포함 → 16 반환
- (5~5): 범위 밖 → 0 반환
결과: 3 + 5 + 16 = 24
단일 원소 업데이트
// arr[idx]의 값을 val로 변경: O(log n)
public void update(int idx, int val) {
update(1, 0, n - 1, idx, val);
}
private void update(int node, int start, int end, int idx, int val) {
if (start == end) {
tree[node] = val; // 리프 노드 업데이트
} else {
int mid = (start + end) / 2;
if (idx <= mid) {
update(2 * node, start, mid, idx, val);
} else {
update(2 * node + 1, mid + 1, end, idx, val);
}
// 자식의 합으로 갱신
tree[node] = tree[2 * node] + tree[2 * node + 1];
}
}
리프 노드에서 루트까지 올라가며 값을 갱신하므로 O(log n)입니다.
Lazy Propagation
구간 전체에 값을 더하는 구간 업데이트 가 필요하다면 어떻게 할까요?
단순하게 하면 구간의 각 원소를 하나씩 업데이트해야 해서 O(n log n)입니다. Lazy Propagation 은 이를 O(log n)으로 줄입니다.
아이디어
업데이트를 바로 적용하지 않고, 나중에 필요할 때 자식에게 전파합니다.
public class LazySegmentTree {
private long[] tree;
private long[] lazy; // 지연된 업데이트 값
private int n;
public LazySegmentTree(int[] arr) {
n = arr.length;
tree = new long[4 * n];
lazy = new long[4 * n]; // 0으로 초기화
build(arr, 1, 0, n - 1);
}
// 지연된 값을 자식에게 전파
private void pushDown(int node, int start, int end) {
if (lazy[node] != 0) {
int mid = (start + end) / 2;
// 왼쪽 자식 업데이트
tree[2 * node] += lazy[node] * (mid - start + 1);
lazy[2 * node] += lazy[node];
// 오른쪽 자식 업데이트
tree[2 * node + 1] += lazy[node] * (end - mid);
lazy[2 * node + 1] += lazy[node];
// 현재 노드의 지연 값 초기화
lazy[node] = 0;
}
}
// 구간 [l, r]에 val을 더하기: O(log n)
public void rangeUpdate(int l, int r, long val) {
rangeUpdate(1, 0, n - 1, l, r, val);
}
private void rangeUpdate(int node, int start, int end, int l, int r, long val) {
if (r < start || end < l) return;
if (l <= start && end <= r) {
// 현재 구간이 완전히 포함 → 지연 업데이트
tree[node] += val * (end - start + 1);
lazy[node] += val;
return;
}
pushDown(node, start, end);
int mid = (start + end) / 2;
rangeUpdate(2 * node, start, mid, l, r, val);
rangeUpdate(2 * node + 1, mid + 1, end, l, r, val);
tree[node] = tree[2 * node] + tree[2 * node + 1];
}
// 구간 합 쿼리도 pushDown 추가
public long query(int l, int r) {
return query(1, 0, n - 1, l, r);
}
private long query(int node, int start, int end, int l, int r) {
if (r < start || end < l) return 0;
if (l <= start && end <= r) return tree[node];
pushDown(node, start, end);
int mid = (start + end) / 2;
return query(2 * node, start, mid, l, r) +
query(2 * node + 1, mid + 1, end, l, r);
}
private void build(int[] arr, int node, int start, int end) {
if (start == end) {
tree[node] = arr[start];
} else {
int mid = (start + end) / 2;
build(arr, 2 * node, start, mid);
build(arr, 2 * node + 1, mid + 1, end);
tree[node] = tree[2 * node] + tree[2 * node + 1];
}
}
}
세그먼트 트리의 변형
구간 합 외에도 다양한 쿼리를 처리할 수 있습니다.
// 구간 최솟값 세그먼트 트리
tree[node] = Math.min(tree[2 * node], tree[2 * node + 1]);
// 구간 최댓값 세그먼트 트리
tree[node] = Math.max(tree[2 * node], tree[2 * node + 1]);
// 구간 GCD 세그먼트 트리
tree[node] = gcd(tree[2 * node], tree[2 * node + 1]);
백엔드/실무 연결
실시간 모니터링 집계
시간대별 요청 수를 관리하면서, 특정 시간 범위의 총 요청 수를 빠르게 조회할 수 있습니다.
// 개념적 예시: 시간대별 요청 수 모니터링
SegmentTree requestCounter = new SegmentTree(new int[86400]); // 1초 단위, 하루
// 특정 시각에 요청 수 증가
requestCounter.update(currentSecond, currentCount + 1);
// 최근 5분간의 총 요청 수
int recentRequests = requestCounter.query(now - 300, now);
데이터베이스 집계
- 시계열 DB에서 구간 집계를 빠르게 처리
- 실시간 대시보드에서 시간 범위별 메트릭 합산
시간/공간 복잡도 정리
| 연산 | 시간 복잡도 |
|---|---|
| 트리 구축 | O(n) |
| 구간 쿼리 | O(log n) |
| 단일 업데이트 | O(log n) |
| 구간 업데이트 (Lazy) | O(log n) |
| 공간 | O(n) |
정리
- 세그먼트 트리는 구간 쿼리와 업데이트를 모두 O(log n) 에 처리합니다.
- 배열을 이진 트리로 분할하여, 필요한 구간만 방문하는 원리입니다.
- Lazy Propagation 을 사용하면 구간 업데이트도 O(log n)에 가능합니다.
- 실시간 모니터링, 시계열 데이터 집계 등에서 활용할 수 있습니다.
- 구간 합뿐 아니라 최솟값, 최댓값, GCD 등 다양한 쿼리에 적용됩니다.
댓글 로딩 중...