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

세그먼트 트리 (Segment Tree)

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

01 Explore How It Works

Interactive Step-by-Step

HOVER OR SCROLL

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 Understand It Simply

For Everyone

🔑Analogy

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

💡In Plain Words

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

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

📍Where It's Used

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

03 Python Implementation

A clean, readable reference implementation of the core logic of 세그먼트 트리 (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 Frequently Asked Questions

FAQ

What is 세그먼트 트리 (Segment Tree)?+

What is the time complexity of 세그먼트 트리 (Segment Tree)?+

The time complexity of 세그먼트 트리 (Segment Tree) is 질의·갱신 O(log n). Follow the step-by-step visualization to see exactly why.

Where is 세그먼트 트리 (Segment Tree) used?+

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

What's a simple analogy for 세그먼트 트리 (Segment Tree)?+

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

→ Trees — see allRelated

🌳트리 순회 (Tree Traversal)

Guide Progress0%