값이 바뀌어도 빠르게! 세그먼트 트리
안녕, 나 코딩냥이다냥! 14장의 누적합 기억나냥? 구간 합을 빠르게 구했지만 값이 하나 바뀌면 누적합을 통째로 다시 만들어야 했다냥.
값이 자주 바뀌면서 구간 질의도 많으면? 그때 쓰는 게 세그먼트 트리라냥.
갱신도, 구간 질의도 둘 다 O(log n) 이라냥.
오늘의 학습 목표
- 누적합이 갱신에 약한 이유를 안다.
- 세그먼트 트리로 구간 합을 구한다.
- 합치는 방법만 바꿔 최솟값·최댓값을 구한다.
- 값 공간 트리로 k번째를 찾는다.
- 값 공간 트리로 x 이하 개수를 센다.
1단계 · 누적합의 약점 (8분)
누적합은 미리 다 더해두는 거였다냥. 그래서 구간 합은 뺄셈 하나로 빨랐다냥. 그런데 값 하나가 바뀌면?
값이 바뀌면 누적합은 뒤가 전부 어긋난다냥.
a[3] 을 바꾸면 pre[3], pre[4], ... 뒤쪽 누적합이 전부 틀려진다냥.
다시 맞추려면 O(n) 이 든다냥. 갱신이 q번이면 O(nq) 라 느리다냥.
오늘 1번 문제를 누적합으로 풀면, 갱신 이후의 구간 합이 틀린다냥.
비유로 이해하기 — 반별 점수판
전교생 점수를 한 줄로 더해두면(누적합), 한 명 점수가 바뀔 때 뒤를 다 고쳐야 한다냥.
대신 반별 합계, 학년별 합계 처럼 묶어서 관리하면? 한 명이 바뀌어도 그 학생이 속한 반 → 학년 → 전교 합계만 고치면 된다냥. 이 "묶음의 나무" 가 세그먼트 트리라냥.
2단계 · 세그먼트 트리의 모양 (12분)
세그먼트 트리는 구간을 반씩 나눈 나무라냥. 잎은 원소 하나, 위로 갈수록 더 큰 구간의 값을 담는다냥.
- 잎 노드 — 원소 하나
- 내부 노드 — 왼쪽 자식 구간과 오른쪽 자식 구간을 합친 값
배열 하나로 담는다냥. 크기를 n 이상의 2의 거듭제곱 size 로 잡고,
잎은 size + i, 부모는 p, 자식은 2p 와 2p+1 이라냥.
size = 1
while size < n:
size *= 2
tree = [0] * (2 * size)
for i in range(n):
tree[size + i] = a[i] # 잎에 원소를 넣는다냥
for i in range(size - 1, 0, -1):
tree[i] = tree[2 * i] + tree[2 * i + 1] # 부모 = 두 자식의 합3단계 · 갱신과 구간 합 (13분)
갱신은 잎을 바꾸고 부모들만 고치는 거라냥. 잎에서 루트까지 한 줄만
고치면 되니 O(log n) 이라냥.
def update(i, v):
p = size + i
tree[p] = v
p >>= 1 # 부모로 올라가며
while p:
tree[p] = tree[2 * p] + tree[2 * p + 1] # 다시 합친다냥
p >>= 1구간 합은 잎 쪽에서 위로 올라가며 필요한 조각만 모은다냥.
def query(l, r): # l..r 포함, 0번부터
res = 0
l += size
r += size + 1
while l < r:
if l & 1: # l 이 오른쪽 자식이면 담고 옮긴다냥
res += tree[l]; l += 1
if r & 1: # r 이 오른쪽 자식이면 담는다냥
r -= 1; res += tree[r]
l >>= 1; r >>= 1 # 한 층 올라간다냥
return res이 반복문 방식은 재귀 없이 구간을 O(log n) 개의 조각으로 나눠 담는다냥.
갱신도 질의도 나무 높이만큼(log n)이라, 값이 자주 바뀌어도 빠르다냥.
오늘 1번 문제라냥.
4단계 · 합치는 방법만 바꾸면 (12분)
세그먼트 트리의 멋진 점이라냥. 합치는 방법(merge) 만 바꾸면 다른 질의가 된다냥. 나무 구조도, 갱신도 그대로라냥.
- 구간 합 —
merge = +, 항등원0 - 구간 최솟값 —
merge = min, 항등원무한대 - 구간 최댓값 —
merge = max, 항등원-무한대
tree[p] = tree[2p] + tree[2p+1] 의 + 를 min 이나 max 로 바꾸고,
빈 값을 나타내는 항등원만 맞춰주면 된다냥. 오늘 1·2·3번이 이거라냥.
항등원을 맞추는 게 중요하다냥.
최솟값에서 "아직 아무것도 안 담은 상태" 는 무한대여야 한다냥 (min 에
영향을 안 주니까). 합에서는 0, 최댓값에서는 -무한대라냥.
항등원을 잘못 잡으면 빈 조각이 답을 오염시킨다냥.
5단계 · 값 공간 트리 (13분)
세그먼트 트리를 원소 위치가 아니라 값에 대해 세우면 새로운 걸 할 수 있다냥. 각 값이 몇 개 있는지를 트리로 관리하는 거라냥.
값 1..M 의 개수를 담은 트리에서, k번째로 작은 값을 찾는다냥.
루트에서 시작해, 왼쪽 자식의 개수가 k 이상이면 왼쪽으로, 아니면
k 에서 왼쪽 개수를 빼고 오른쪽으로 내려간다냥.
def kth(k):
node = 1
while node < size:
left = tree[2 * node]
if k <= left:
node = 2 * node # k번째가 왼쪽에 있다냥
else:
k -= left
node = 2 * node + 1 # 오른쪽으로, k 를 줄여서냥
return node - size # 잎에 도착 = 그 값잎까지 O(log M) 에 내려간다냥. 오늘 4번 문제라냥.
같은 값 공간 트리로 "x 이하가 몇 개냥?" 도 답한다냥. 그건 그냥 값
1..x 의 구간 합 질의라냥. 오늘 5번 문제라냥. 트리는 같고, k번째
내려가기 대신 구간 합을 쓸 뿐이라냥.
오늘 배운 내용 정리
먼저 스스로 답해보고, "정답 보기"를 눌러서 맞는지 확인해보자냥!
이제 직접 풀어볼 차례다냥
오늘 문제는 다섯 개라냥. 1번 구간 합, 2번 최솟값, 3번 최댓값 (셋은 merge 만 다르다냥), 4번 k번째 찾기, 5번 x 이하 개수라냥.
1번을 제대로 짜두면 2·3번은 두 줄만 바꾸면 된다냥. 4·5번은 트리를 값에 세우는 새로운 발상이라냥. 가보자냥~