---
title: "세그먼트 트리: 구간 결과를 합칠 수 있을 때의 자료구조"
author: "Lee"
published_at: "2026-10-26T06:55:00.836Z"
updated_at: "2026-09-30T09:49:46.836Z"
tags: ["컴퓨터공학","자료구조"]
canonical_url: "https://ariser.io/@writer_a1cd615ab19e/%EC%84%B8%EA%B7%B8%EB%A8%BC%ED%8A%B8-%ED%8A%B8%EB%A6%AC-%EA%B5%AC%EA%B0%84-%EA%B2%B0%EA%B3%BC%EB%A5%BC-%ED%95%A9%EC%B9%A0-%EC%88%98-%EC%9E%88%EC%9D%84-%EB%95%8C%EC%9D%98-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0"
ai_assisted: false
---

# 세그먼트 트리: 구간 결과를 합칠 수 있을 때의 자료구조

[원문](https://ariser.io/@writer_a1cd615ab19e/%EC%84%B8%EA%B7%B8%EB%A8%BC%ED%8A%B8-%ED%8A%B8%EB%A6%AC-%EA%B5%AC%EA%B0%84-%EA%B2%B0%EA%B3%BC%EB%A5%BC-%ED%95%A9%EC%B9%A0-%EC%88%98-%EC%9E%88%EC%9D%84-%EB%95%8C%EC%9D%98-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0)

세그먼트 트리는 배열의 구간을 계층적으로 나누고 각 구간의 합, 최솟값 같은 결과를 저장한다. 원소 하나가 바뀌었을 때 모든 구간을 다시 계산하지 않고 그 원소를 포함하는 조상 구간만 갱신한다.

![배열 2·1·3·4의 구간 합을 저장하고 인덱스 1부터 2의 합 4를 구하는 세그먼트 트리](/api/v1/media/58cb3e54-93e1-44f9-a421-e69ed52bdd07)

*각 내부 노드는 담당 구간의 집계값을 저장한다.*

### 결합 규칙이 구조를 만든다

루트는 전체 구간, 자식은 그 절반을 담당한다. 구간 합이라면 부모 값은 두 자식 합이고 구간 최솟값이라면 두 자식 중 작은 값이다. 어떤 방식으로 묶어도 같은 결과가 나오는 결합법칙과 빈 구간의 항등원이 필요하다.

아래 반복형 구현은 길이를 2의 거듭제곱으로 맞춘 구간 합 트리다. query(left,right)는 반열린 구간 [left,right)의 합을 반환한다.

```python
size = 1
while size < len(values):
    size *= 2
tree = [0] * (2 * size)
tree[size:size + len(values)] = values
for node in range(size - 1, 0, -1):
    tree[node] = tree[2 * node] + tree[2 * node + 1]

def query(left, right):
    left += size
    right += size
    result = 0
    while left < right:
        if left % 2 == 1:
            result += tree[left]
            left += 1
        if right % 2 == 1:
            right -= 1
            result += tree[right]
        left //= 2
        right //= 2
    return result
```

경계에 걸친 노드를 결과에 넣고 나머지를 부모 구간으로 올리므로 구간을 서로 겹치지 않는 몇 개 노드로 덮는다. 합은 교환법칙도 있지만 문자열 연결처럼 순서가 중요한 연산에는 왼쪽과 오른쪽 누적 결과를 나눠 결합해야 한다.

### 한 원소가 바뀌는 경로

[2,1,4,3]의 합은 10이다. 인덱스 1을 5로 바꾸면 해당 잎, [0,2) 구간, 전체 [0,4) 구간만 다시 계산해 전체 합을 14로 만든다. 다른 가지는 변하지 않는다.

초기 구성 시간 O(n), 저장 공간 O(n), 점 갱신과 구간 질의는 O(log n)이다. 크기를 가장 가까운 2의 거듭제곱으로 올려도 상수배 공간이다. 요청 범위가 배열 경계 안에 있는지는 별도로 검사한다.

구간 전체에 값을 더하는 갱신을 점 갱신으로 반복하면 느려진다. 지연 전파는 구간 변경 정보를 노드에 보류하여 이 작업을 확장하지만, 집계 값과 태그 결합을 정확히 설계해야 한다. 단순 합 트리에 어떤 변경도 붙일 수 있는 것은 아니다.

최솟값, 최댓값, 최대공약수 등에도 사용할 수 있지만 구간 중앙값처럼 두 결과만 간단히 합칠 수 없는 문제에는 추가 구조가 필요하다. 먼저 어떤 정보를 저장해야 자식의 결과로 부모의 결과를 계산할 수 있는지 확인하는 것이 세그먼트 트리 설계의 출발점이다.

### 참고 자료

- [MIT OpenCourseWare · Introduction to Algorithms](https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-fall-2011/)