세그먼트 트리는 이름부터 어렵게 느껴지는 대표 자료구조입니다. 많은 사람이 구현 코드가 길다는 이유로 먼저 겁을 먹고, 왜 이런 구조가 필요한지 감을 잡기 전에 포기합니다. 하지만 세그먼트 트리를 이해하는 핵심은 트리 모양이 아니라, 어떤 병목을 해결하려는지 보는 데 있습니다.
이번 글에서는 세그먼트 트리를 트릭처럼 소개하지 않고, 구간 질의와 업데이트가 동시에 자주 나오는 문제를 버티게 만드는 구조로 설명하겠습니다.
누적합으로 충분할 때와 아닌 때
누적합은 구간 합 질의만 빠르게 하고 싶을 때 매우 강력합니다. 배열이 고정되어 있고 업데이트가 거의 없다면 누적합만으로 충분한 경우가 많습니다.
문제는 값이 계속 바뀌는 상황입니다. 예를 들어 특정 인덱스 값이 바뀌고, 그 뒤에도 여러 구간 합 질의를 계속 해야 한다면 누적합 배열을 매번 다시 만드는 비용이 커집니다. 바로 이 지점에서 세그먼트 트리를 생각해야 합니다.
세그먼트 트리는 무엇을 저장하나
세그먼트 트리는 배열의 한 칸만 저장하는 것이 아니라, 특정 구간의 요약값을 각 노드에 저장합니다. 예를 들어 루트는 전체 구간의 합, 그 아래 노드는 절반 구간의 합, 그 아래는 더 작은 구간의 합을 들고 있는 식입니다.
즉 배열을 계속 잘게 나눠 가면서 각 구간의 핵심 정보를 계층적으로 저장한다고 보면 됩니다. 그래서 필요한 구간에만 접근해도 전체 답을 빠르게 만들 수 있습니다.
구간 질의는 왜 빠를까
구간 [l, r]의 합을 구하고 싶을 때, 세그먼트 트리는 해당 구간을 완전히 덮는 노드들만 선택해서 결과를 조합합니다. 배열을 처음부터 끝까지 매번 다시 더하지 않아도 되는 이유가 여기에 있습니다.
즉 질의는 “필요한 구간 노드만 방문하고 나머지는 건너뛴다”는 점에서 빠릅니다.
업데이트는 왜 전체를 다시 안 고쳐도 될까
어떤 인덱스 값이 바뀌면 그 인덱스를 포함하는 구간 노드들만 다시 계산하면 됩니다. 즉 한 칸 값이 바뀌었다고 해서 전체 prefix sum을 전부 다시 만들 필요가 없습니다.
이 점 때문에 세그먼트 트리는 “질의만 빠른 구조”가 아니라 “질의와 업데이트를 둘 다 버티는 구조”로 이해하는 편이 맞습니다.
def query(node, start, end, left, right):
if right < start or end < left:
return 0
if left <= start and end <= right:
return tree[node]
mid = (start + end) // 2
return query(node*2, start, mid, left, right) + query(node*2+1, mid+1, end, left, right)
def update(node, start, end, idx, value):
if idx < start or idx > end:
return
if start == end:
tree[node] = value
return
mid = (start + end) // 2
update(node*2, start, mid, idx, value)
update(node*2+1, mid+1, end, idx, value)
tree[node] = tree[node*2] + tree[node*2+1]코드는 길어 보여도 핵심은 단순합니다. query는 필요한 구간만 내려가고, update는 영향을 받는 구간만 다시 올려 계산합니다. 이 두 동작이 세그먼트 트리의 본질입니다.
문제에서 어떤 신호가 보이면 세그먼트 트리일까
- 구간 합/최솟값/최댓값 질의가 많다
- 중간에 값 업데이트가 반복된다
- 누적합으로는 업데이트 비용이 너무 크다
- 배열 전체를 다시 계산하는 방식이 비효율적이다
이 신호가 보이면 세그먼트 트리 가능성이 큽니다. 특히 “query도 많고 update도 많다”는 문장이 핵심입니다.
헷갈리는 포인트
- 세그먼트 트리는 모든 값을 저장하는 것이 아니라 구간 요약값을 저장한다
- 트리 모양 자체보다 구간 분할/병합 아이디어가 더 중요하다
- 누적합은 update가 약하고, 세그먼트 트리는 update까지 버틴다
- lazy propagation은 별도 심화 주제이며 기본 세그트리와 구분해야 한다
좌표가 너무 큰 문제에서는 좌표 압축 글과도 자주 연결됩니다. 또 구간 합만 빠르게 보고 싶을 때는 누적합 글이 더 단순한 해법일 수 있습니다.
마무리
세그먼트 트리의 핵심은 트리라는 모양보다, 구간을 나눠 저장해 query와 update를 동시에 빠르게 만드는 데 있습니다.
즉 구간 질의와 업데이트가 함께 많아지는 순간 세그먼트 트리를 떠올릴 수 있어야 합니다.
