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

세그먼트 트리 (Segment Tree)

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

01 알고리즘 작동 원리 탐색

Interactive Step-by-Step

TAP OR HOVER

Segment Tree · 구간 합

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

Logic Node1 / 6

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 # 부분 합 합치기

02 쉽게 이해하기

For Everyone

🔑비유

구간별 합계를 미리 적어둔 다단계 영수증 — 부분 합을 즉시 꺼냅니다.

💡쉽게 말하면

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

값 하나가 바뀌어도, 넓은 구간의 합을 물어봐도 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

Guide Progress0%