전체 흐름
LCA 문제
↓ 오일러 투어
배열로 변환
↓ RMQ로 환원
구간 최솟값 문제
↓ Segment Tree 또는 Sparse Table
O(log n) 또는 O(1) 쿼리
RMQ (Range Minimum Query)
배열에서 특정 구간 [l, r]의 최솟값을 구하는 문제.
| 방법 | 전처리 | 쿼리 | 업데이트 |
|---|---|---|---|
| 단순 탐색 | O(1) | O(n) | O(1) |
| 세그먼트 트리 | O(n) | O(log n) | O(log n) |
| Sparse Table | O(n log n) | O(1) | 불가 |
Segment Tree
핵심 아이디어
구간별 최솟값(또는 합 등)을 트리 구조로 미리 저장해두는 자료구조.
[0~7] : 1
├── [0~3] : 3
│ ├── [0~1] : 5
│ └── [2~3] : 3
└── [4~7] : 1
├── [4~5] : 1
└── [6~7] : 2
각 노드는 “내 담당 구간의 최솟값” 을 저장한다.
배열로 저장 (힙 구조)
트리를 배열로 저장할 때 포인터 없이 인덱스만으로 이동한다.
tree[k]의 부모 →tree[k/2]tree[k]의 자식 →tree[2k],tree[2k+1]
배열 크기는 4n으로 잡는 것이 국룰이다. 이유는 아래와 같다.
- 트리 높이
h = ceil(log2(n)) - 최대 인덱스 =
2^(h+1) - 1 h <= log2(n) + 1이므로 최대 인덱스<= 2^(log2(n)+2) = 4n
n이 2의 거듭제곱보다 1만 커도 레벨이 하나 더 생겨 배열이 2배로 뛰기 때문에 4n으로 여유 있게 잡는다.
구현 (Python)
n = len(arr)
tree = [0] * (4 * n)
def build(node, s, e):
if s == e:
tree[node] = arr[s]
return
mid = (s + e) // 2
build(2*node, s, mid)
build(2*node+1, mid+1, e)
tree[node] = min(tree[2*node], tree[2*node+1])
def query(node, s, e, l, r):
if l > r:
return float('inf')
if s == l and e == r:
return tree[node]
mid = (s + e) // 2
return min(
query(2*node, s, mid, l, min(r, mid)),
query(2*node+1, mid+1, e, max(l, mid+1), r)
)
def update(node, s, e, idx, val):
if s == e:
tree[node] = val
return
mid = (s + e) // 2
if idx <= mid: update(2*node, s, mid, idx, val)
else: update(2*node+1, mid+1, e, idx, val)
tree[node] = min(tree[2*node], tree[2*node+1])
쿼리 원리 — 각 레벨에서 최대 2개 노드
쿼리 범위 [l, r]에는 왼쪽 끝점 l, 오른쪽 끝점 r 딱 2개뿐이다. “걸쳐있음(일부만 겹침)“은 이 두 끝점 근처에서만 발생하고, 중간 노드들은 전부 완전 포함 또는 완전 제외로 바로 처리된다.
따라서 각 레벨에서 더 내려가야 하는 노드는 최대 2개이고, 트리 높이가 O(log n)이므로 전체 쿼리 시간복잡도는 O(log n)이다.
쿼리 함수의 세 가지 케이스
① left > right → 완전 제외, inf 리턴 (min에 영향 없음)
② s==l, e==r → 완전 포함, tree[node] 바로 리턴
③ 그 외 → 걸쳐있음, 반으로 쪼개 재귀
쿼리 [2~3]에서 inf가 발생하는 흐름:
Sparse Table
핵심 아이디어
st[i][j] = A[i]부터 2^j개의 최솟값을 미리 전처리해두고, 쿼리를 2개의 구간으로 덮어 O(1)에 해결한다.
i: 시작 인덱스j: 구간 길이의 지수 (2^j개)
전처리 — DP로 O(n log n)
st[i][0] = A[i] # 길이 1짜리
# 작은 구간 2개를 합쳐 큰 구간 만들기
st[i][j] = min(st[i][j-1], st[i + 2^(j-1)][j-1])
# 왼쪽 절반 오른쪽 절반 시작점
오른쪽 절반의 시작점이 i + 2^(j-1)인 이유: 왼쪽이 i부터 2^(j-1)개를 차지하므로 오른쪽은 그 다음인 i + 2^(j-1)부터 시작한다.
쿼리 — O(1)
def query(L, R):
length = R - L + 1
k = floor(log2(length))
return min(st[L][k], st[R - 2**k + 1][k])
길이 ℓ = R - L + 1에 대해 k = floor(log2(ℓ))로 잡으면, 길이 2^k짜리 구간 2개가 [L, R]을 완전히 덮는다.
쿼리 [3 ~ 13], 길이 11, k=3, 2^k=8
왼쪽: [3 ~ 10] (3부터 8개)
오른쪽: [6 ~ 13] (13-8+1=6 부터 8개)
겹치는 부분이 있어도 최솟값이라 상관없음
두 구간이 겹쳐도 되는 이유: 최솟값은 겹쳐도 결과가 동일하기 때문이다.
인터랙티브 — 직접 쿼리해보기
업데이트가 불가능한 이유
값 하나가 바뀌면 그 값을 포함하는 st[i][j] 칸을 전부 다시 계산해야 한다. 이는 사실상 전처리 O(n log n)을 다시 하는 것과 같다.
Segment Tree vs Sparse Table
| Segment Tree | Sparse Table | |
|---|---|---|
| 전처리 | O(n) | O(n log n) |
| 쿼리 | O(log n) | O(1) |
| 업데이트 | O(log n) | 불가 |
선택 기준:
- 배열이 고정 (쿼리만 있음) → Sparse Table
- 배열이 바뀜 (업데이트 + 쿼리) → Segment Tree
LCA 문제에서 트리 구조가 고정이면 오일러 투어 배열도 불변이므로 Sparse Table이 최적이다.
LCA와의 연결
LCA(u, v)
= 오일러 투어 배열에서 u와 v 사이 구간의 최솟값(깊이 기준)에 해당하는 노드
= RMQ(euler_tour, first[u], first[v])
Sparse Table로 전처리하면 LCA 쿼리를 O(1)에 처리할 수 있다.