Algorithm Guidecomplexity: 질의·갱신 O(log n)

세그먼트 트리 (Segment Tree)

구간의 합·최솟값 등을 빠르게 구하기 위한 트리입니다. 각 노드가 한 구간을 담당하며, 점 갱신과 구간 질의를 모두 O(log n)에 처리해 누적 합 배열의 갱신 약점을 보완합니다.

01세그먼트 트리 (Segment Tree)

알고리즘 작동 원리 탐색

세그먼트 트리. 배열 [1, 3, 5, 7] 위에서, 각 노드가 자기 구간의 합을 들고 있습니다.

리프는 원소 자신이고, 부모는 두 자식의 합입니다. 위로 합쳐 루트는 전체 합 16이 됩니다.

query(1, 3) · 인덱스 1~3의 합을 구합니다. 루트 [0,3]에서 내려가기 시작합니다.

왼쪽 [0,1]은 질의 구간과 일부만 겹칩니다. 더 내려가 [1,1]=3만 채택합니다.

오른쪽 [2,3]은 질의 구간에 완전히 포함됩니다. 더 내려가지 않고 통째로 12를 채택합니다.

채택한 조각을 합칩니다 · 3 + 12 = 15. 잎까지 다 더하지 않고 O(log n)에 구간 합을 구했습니다.

Live Python

1def query(node, node_lo, node_hi, lo, hi):

2 if hi < node_lo or node_hi < lo:

3 return 0 # 겹치지 않음

4 if lo <= node_lo and node_hi <= hi:

5 return tree[node] # 완전히 포함 → 통째로

6 mid = (node_lo + node_hi) // 2

7 left = query(2*node, node_lo, mid, lo, hi)

8 right = query(2*node+1, mid + 1, node_hi, lo, hi)

9 return left + right # 부분 합 합치기

1 / 6

02 쉽게 이해하기

For Everyone

🔑핵심 동작

구간을 반씩 쪼개 각 노드에 그 구간의 합을 저장합니다. 구간 합과 값 갱신을 둘 다 O(log n) 에 처리합니다.

💡쉽게 말하면

각 노드가 특정 구간의 합(또는 최솟값)을 들고 있는 트리예요.

값 하나가 바뀌어도, 넓은 구간의 합을 물어봐도 O(log n)에 답합니다.

📍어디에 쓰나

–구간 합·최솟값 질의
–실시간 순위·통계
–게임 점수판

03 파이썬 구현 코드

세그먼트 트리 (Segment Tree)의 핵심 로직을 담은 표준 구현 예시입니다. 가급적 간결하고 읽기 쉬운 코드로 작성되었습니다.

core_implementation.py

class SegmentTree:
    def __init__(self, data):
        self.n = len(data)
        self.tree = [0] * (2 * self.n)
        for i in range(self.n):
            self.tree[self.n + i] = data[i]
        for i in range(self.n - 1, 0, -1):
            self.tree[i] = self.tree[2*i] + self.tree[2*i + 1]

    def query(self, l, r):   # 구간 합 [l, r)
        res = 0
        l += self.n; r += self.n
        while l < r:
            if l & 1:
                res += self.tree[l]; l += 1
            if r & 1:
                r -= 1; res += self.tree[r]
            l >>= 1; r >>= 1
        return res

04 자주 묻는 질문

FAQ

세그먼트 트리 (Segment Tree)란 무엇인가요?+

세그먼트 트리 (Segment Tree)의 시간복잡도는 어떻게 되나요?+

세그먼트 트리 (Segment Tree)의 시간복잡도는 질의·갱신 O(log n) 입니다. 시각화의 단계별 진행을 따라가며 왜 이런 복잡도가 나오는지 직접 확인할 수 있습니다.

세그먼트 트리 (Segment Tree)은(는) 어디에 사용하나요?+

구간 합·최솟값 질의, 실시간 순위·통계, 게임 점수판.

세그먼트 트리 (Segment Tree)를 쉽게 비유하면?+

구간을 반씩 쪼개 각 노드에 그 구간의 합을 저장합니다. 구간 합과 값 갱신을 둘 다 O(log n) 에 처리합니다.

→ 트리 전체 보기Related

🌳트리 순회 (Tree Traversal)