세그먼트 트리 (Segment Tree)

2026년 6월 24일 · 수정 2026년 6월 24일 · 📖 약 5분 · 1,387자/단어 #algorithm #data-structure #tree

정의

세그먼트 트리 (Segment Tree) 는 배열의 구간 쿼리 (range query) 와 점 갱신 (point update) 를 모두 O(log N) 에 처리하는 이진 트리 자료구조.

리프 노드가 원소, 내부 노드가 구간의 합/최솟값/최댓값/GCD 등 결합 가능한 연산 (associative operation) 결과를 저장. 높이 ⌈log₂ N⌉ 의 완전 이진 트리.

누적 합은 O(1) 쿼리지만 갱신이 O(N), Fenwick Tree (BIT) 는 합/XOR 만 가능. 세그먼트 트리는 임의 결합 연산 을 O(log N) / O(log N) 로 일반화.

문제 상황과 동기

길이 N 배열에서:

쿼리: sum(l, r), min(l, r), max(l, r) 등 Q 개
갱신: a[i] = x 업데이트 U 개

방식	쿼리	갱신	비고
naive	O(N)	O(1)	쿼리마다 순회
[[Prefix Sum	누적 합]]	O(1)	O(N)
Segment Tree	O(log N)	O(log N)	균형

핵심 통찰: 구간을 이진 분할하면 임의 구간이 O(log N) 개 노드의 합집합. 각 노드가 관할 구간의 연산 결과를 캐싱하므로, 경로상 노드만 확인.

PS에서 “구간 합/최소/최대 쿼리 + 업데이트” 가 동시에 나오면 세그먼트 트리 또는 레이지 프로파게이션.

시각화

핵심 아이디어

invariant: 노드 [l, r] 의 값 = 구간 [l, r] 의 연산 결과.

tree[node] = op(tree[2*node], tree[2*node+1])

op 는 결합 법칙 만족 (associative): op(a, op(b, c)) = op(op(a, b), c). 대표 예: +, min, max, gcd, lcm, XOR.

구조:

1-indexed 완전 이진 트리. tree[1] = 전체 구간.
노드 i 의 왼쪽 자식 = 2i, 오른쪽 자식 = 2i+1.
리프 노드 N 개 → 전체 노드 ≤ 4N (보통 4N 배열).

쿼리 [L, R]:

현재 노드 [l, r] 이 [L, R] 에 완전히 포함 → 즉시 반환.
겹치지 않으면 스킵.
부분 겹침 → 왼쪽/오른쪽 재귀, 결과 병합.

갱신 a[idx] = val:

리프 노드까지 내려가 val 로 갱신.
돌아오며 조상 노드들 모두 재계산.

알고리즘

빌드

build(node, l, r):
    if l = r:
        tree[node] = a[l]
    else:
        mid = (l + r) / 2
        build(2*node, l, mid)
        build(2*node+1, mid+1, r)
        tree[node] = op(tree[2*node], tree[2*node+1])

쿼리

query(node, l, r, L, R):
    if r < L or R < l:    # 범위 벗어남
        return identity
    if L ≤ l and r ≤ R:   # 완전 포함
        return tree[node]
    mid = (l + r) / 2
    left = query(2*node, l, mid, L, R)
    right = query(2*node+1, mid+1, r, L, R)
    return op(left, right)

점 갱신

update(node, l, r, idx, val):
    if l = r:             # 리프
        tree[node] = val
    else:
        mid = (l + r) / 2
        if idx ≤ mid:
            update(2*node, l, mid, idx, val)
        else:
            update(2*node+1, mid+1, r, idx, val)
        tree[node] = op(tree[2*node], tree[2*node+1])

구현

// 구간 합 세그먼트 트리, 1-indexed
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

class SegTree {
  vector<ll> tree;
  int n;
  
  void build(vector<ll>& a, int node, int l, int r) {
      if (l == r) {
          tree[node] = a[l];
      } else {
          int mid = (l + r) / 2;
          build(a, 2*node, l, mid);
          build(a, 2*node+1, mid+1, r);
          tree[node] = tree[2*node] + tree[2*node+1];
      }
  }
  
  ll query(int node, int l, int r, int L, int R) {
      if (r < L || R < l) return 0;
      if (L <= l && r <= R) return tree[node];
      int mid = (l + r) / 2;
      return query(2*node, l, mid, L, R) + query(2*node+1, mid+1, r, L, R);
  }
  
  void update(int node, int l, int r, int idx, ll val) {
      if (l == r) {
          tree[node] = val;
      } else {
          int mid = (l + r) / 2;
          if (idx <= mid) update(2*node, l, mid, idx, val);
          else update(2*node+1, mid+1, r, idx, val);
          tree[node] = tree[2*node] + tree[2*node+1];
      }
  }
  
public:
  SegTree(vector<ll>& a) : n(a.size() - 1), tree(4 * n) {
      if (n > 0) build(a, 1, 1, n);
  }
  
  ll query(int l, int r) { return query(1, 1, n, l, r); }
  void update(int idx, ll val) { update(1, 1, n, idx, val); }
};

int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  int n, q; cin >> n >> q;
  vector<ll> a(n + 1);
  for (int i = 1; i <= n; i++) cin >> a[i];
  
  SegTree seg(a);
  while (q--) {
      int t; cin >> t;
      if (t == 1) {
          int idx; ll val; cin >> idx >> val;
          seg.update(idx, val);
      } else {
          int l, r; cin >> l >> r;
          cout << seg.query(l, r) << "\n";
      }
  }
}

# 구간 합 세그먼트 트리
import sys
input = sys.stdin.readline

class SegTree:
  def __init__(self, a):
      self.n = len(a) - 1  # 1-indexed
      self.tree = [0] * (4 * self.n)
      if self.n > 0:
          self._build(a, 1, 1, self.n)
  
  def _build(self, a, node, l, r):
      if l == r:
          self.tree[node] = a[l]
      else:
          mid = (l + r) // 2
          self._build(a, 2*node, l, mid)
          self._build(a, 2*node+1, mid+1, r)
          self.tree[node] = self.tree[2*node] + self.tree[2*node+1]
  
  def query(self, L, R):
      return self._query(1, 1, self.n, L, R)
  
  def _query(self, node, l, r, L, R):
      if r < L or R < l:
          return 0
      if L <= l and r <= R:
          return self.tree[node]
      mid = (l + r) // 2
      return self._query(2*node, l, mid, L, R) + self._query(2*node+1, mid+1, r, L, R)
  
  def update(self, idx, val):
      self._update(1, 1, self.n, idx, val)
  
  def _update(self, node, l, r, idx, val):
      if l == r:
          self.tree[node] = val
      else:
          mid = (l + r) // 2
          if idx <= mid:
              self._update(2*node, l, mid, idx, val)
          else:
              self._update(2*node+1, mid+1, r, idx, val)
          self.tree[node] = self.tree[2*node] + self.tree[2*node+1]

n, q = map(int, input().split())
a = [0] + list(map(int, input().split()))
seg = SegTree(a)

out = []
for _ in range(q):
  t, *args = map(int, input().split())
  if t == 1:
      idx, val = args
      seg.update(idx, val)
  else:
      l, r = args
      out.append(str(seg.query(l, r)))
print("\n".join(out))

// 구간 합 세그먼트 트리
import java.util.*;
import java.io.*;

class SegTree {
  long[] tree;
  int n;
  
  SegTree(long[] a) {
      n = a.length - 1;
      tree = new long[4 * n];
      if (n > 0) build(a, 1, 1, n);
  }
  
  void build(long[] a, int node, int l, int r) {
      if (l == r) {
          tree[node] = a[l];
      } else {
          int mid = (l + r) / 2;
          build(a, 2*node, l, mid);
          build(a, 2*node+1, mid+1, r);
          tree[node] = tree[2*node] + tree[2*node+1];
      }
  }
  
  long query(int L, int R) {
      return query(1, 1, n, L, R);
  }
  
  long query(int node, int l, int r, int L, int R) {
      if (r < L || R < l) return 0;
      if (L <= l && r <= R) return tree[node];
      int mid = (l + r) / 2;
      return query(2*node, l, mid, L, R) + query(2*node+1, mid+1, r, L, R);
  }
  
  void update(int idx, long val) {
      update(1, 1, n, idx, val);
  }
  
  void update(int node, int l, int r, int idx, long val) {
      if (l == r) {
          tree[node] = val;
      } else {
          int mid = (l + r) / 2;
          if (idx <= mid) update(2*node, l, mid, idx, val);
          else update(2*node+1, mid+1, r, idx, val);
          tree[node] = tree[2*node] + tree[2*node+1];
      }
  }
}

public class Main {
  public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine());
      int n = Integer.parseInt(st.nextToken());
      int q = Integer.parseInt(st.nextToken());
      
      long[] a = new long[n + 1];
      st = new StringTokenizer(br.readLine());
      for (int i = 1; i <= n; i++)
          a[i] = Long.parseLong(st.nextToken());
      
      SegTree seg = new SegTree(a);
      StringBuilder sb = new StringBuilder();
      
      while (q-- > 0) {
          st = new StringTokenizer(br.readLine());
          int t = Integer.parseInt(st.nextToken());
          if (t == 1) {
              int idx = Integer.parseInt(st.nextToken());
              long val = Long.parseLong(st.nextToken());
              seg.update(idx, val);
          } else {
              int l = Integer.parseInt(st.nextToken());
              int r = Integer.parseInt(st.nextToken());
              sb.append(seg.query(l, r)).append('\n');
          }
      }
      System.out.print(sb);
  }
}

stdin

결과

6
16
22

복잡도

항목	값
빌드	O(N)
쿼리	O(log N)
점 갱신	O(log N)
공간	O(N), 실제 4N 배열

트리 높이 = ⌈log₂ N⌉, 각 연산이 경로상 노드만 방문.

변형 / 활용

1. Min / Max 세그먼트 트리

// op 를 min 으로 변경
tree[node] = min(tree[2*node], tree[2*node+1]);

identity는 INF (min), -INF (max).

2. GCD / LCM

ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
tree[node] = gcd(tree[2*node], tree[2*node+1]);

3. 구간 갱신 (Lazy Propagation)

점 갱신이 아니라 [l, r] += k 같은 구간 갱신 이 필요하면 레이지 프로파게이션 추가. O(log N) 유지.

4. 2D 세그먼트 트리

세그먼트 트리의 각 노드가 또 다른 세그먼트 트리. 2D 구간 쿼리/갱신 O(log² N).

5. Persistent Segment Tree

과거 버전 유지. 함수형 자료구조로 O(log N) 공간/시간 추가.

함정

1. 배열 크기

tree[4 * N] 이 안전. 2 * N 으로 하면 일부 케이스 overflow.

2. 1-indexed vs 0-indexed

쿼리 범위 [L, R] 이 1-indexed 인지 0-indexed 인지 일관성 유지. 헷갈리면 버그.

3. identity 원소

합: 0, 곱: 1, min: INF, max: -INF, gcd: 0, XOR: 0. 잘못 설정하면 틀린 답.

4. long long 범위

N=10^5, 각 원소 10^9 이면 합이 10^14. C++ 에서 int 로 하면 오버플로우.

5. 재귀 깊이

Python 은 재귀 한도 (기본 1000). sys.setrecursionlimit(10**6) 필요.

BOJ 연습 문제

번호	제목	정답률	링크
BOJ 2042	구간 합 구하기	27.3%	kokoa-lab
BOJ 10868	최솟값	35.8%	kokoa-lab
BOJ 2357	최솟값과 최댓값	35.2%	kokoa-lab
BOJ 1275	커피숍2	33.5%	kokoa-lab

참고

이 글의 용어 (4개)

누적 합 (Prefix Sum)algorithm: 정의 누적 합 (Prefix Sum) 은 배열 에 대해 (또는 1-indexed ) 을 미리 계산해 두고, 임의 구간 합 을 O(1) 에 구하는 정형. 문제 풀이에서 "구간 N …
레이지 프로파게이션 (Lazy Propagation)algorithm: 정의 레이지 프로파게이션 (Lazy Propagation) 은 세그먼트 트리의 확장으로, 구간 갱신 (range update) 와 구간 쿼리 (range query) 를 모두 O…
희소 배열 (Sparse Table)algorithm: 정의 희소 배열 (Sparse Table) 은 정적 배열에서 결합 법칙을 만족하는 idempotent 연산 (min, max, gcd, lcm 등) 의 구간 쿼리를 O(1) 시간…
Fenwick Tree (Binary Indexed Tree): 구간 합 O(log N)algorithm: 정의 Fenwick Tree (또는 BIT, Binary Indexed Tree) 는 배열의 prefix sum 을 O(log N) 에 갱신·조회 하는 자료구조입니다. Peter…