세그먼트 트리

어떤 문제를 푸는가

배열에 대해 다음 두 연산을 둘 다 빠르게 처리해야 할 때 씁니다.

• 점 갱신 — 한 원소의 값을 바꾼다.
• 구간 질의 — 구간 \([l, r]\)의 합/최솟값/최댓값 등을 구한다.

누적 합은 질의가 \(O(1)\)이지만 갱신이 \(O(N)\)입니다. 단순 배열은 갱신이 \(O(1)\)
이지만 질의가 \(O(N)\)입니다. 세그먼트 트리는 둘 다 \(O(\log N)\) 으로 만듭니다.

구조 — 구간을 반씩 쪼갠 이진 트리

루트가 전체 구간 \([0, N-1]\)을 담고, 각 노드는 자기 구간을 절반으로 나눠 두
자식에게 맡깁니다. 리프는 원소 하나에 대응합니다. 각 내부 노드는 자기 구간의
요약값(예: 합)을 저장합니다.

         [0,3]=합
        /       \
   [0,1]=합   [2,3]=합
   /   \       /   \
 [0]  [1]    [2]   [3]

높이가 \(O(\log N)\)이라 루트에서 리프까지 경로가 짧습니다. 배열로 구현하면
노드 \(i\)의 자식은 \(2i\), \(2i+1\)입니다.

질의 — 구간을 노드들로 분해

질의 구간 \([l, r]\)을 트리의 노드들이 덮는 부분 구간들의 합집합 으로
쪼갭니다. 임의의 구간은 \(O(\log N)\)개의 노드로 정확히 덮이므로, 그 노드들의
요약값을 합치면 답이 나옵니다.

• 노드 구간이 질의 구간에 완전히 포함 → 그 노드 값을 바로 사용(더 안 내려감).
• 전혀 안 겹침 → 무시.
• 부분만 겹침 → 두 자식으로 내려가 재귀.

갱신 — 리프에서 위로

한 원소를 바꾸면, 그 리프부터 루트까지의 경로 위 노드들만 요약값을 다시
계산합니다. 경로 길이가 \(O(\log N)\)이라 갱신도 \(O(\log N)\)입니다.

복잡도

결합 연산의 조건 — 결합법칙

세그먼트 트리가 다룰 수 있는 연산은 결합법칙 을 만족해야 합니다:
\((a \oplus b) \oplus c = a \oplus (b \oplus c)\). 합, 최솟값, 최댓값, GCD,
곱 등이 해당합니다. "구간 내 K번째 수" 같은 건 단순 결합이 안 되어 변형이
필요합니다. 다음 강의에서 구현을 봅니다.

배열 기반 구현 (C++, 합)

크기 \(4N\)짜리 배열로 트리를 표현합니다. 재귀가 가장 이해하기 쉽습니다.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n;
vector<ll> seg, a;

void build(int node, int s, int e) {     // [s, e]
    if (s == e) { seg[node] = a[s]; return; }
    int m = (s + e) / 2;
    build(2 * node, s, m);
    build(2 * node + 1, m + 1, e);
    seg[node] = seg[2 * node] + seg[2 * node + 1];   // 결합
}

void update(int node, int s, int e, int idx, ll val) {
    if (s == e) { seg[node] = val; return; }
    int m = (s + e) / 2;
    if (idx <= m) update(2 * node, s, m, idx, val);
    else update(2 * node + 1, m + 1, e, idx, val);
    seg[node] = seg[2 * node] + seg[2 * node + 1];
}

ll query(int node, int s, int e, int l, int r) {     // [l, r] 합
    if (r < s || e < l) return 0;          // 전혀 안 겹침 → 항등원
    if (l <= s && e <= r) return seg[node]; // 완전히 포함
    int m = (s + e) / 2;
    return query(2 * node, s, m, l, r)
         + query(2 * node + 1, m + 1, e, l, r);
}

int main() {
    cin >> n;
    a.assign(n, 0); seg.assign(4 * n, 0);
    for (auto& x : a) cin >> x;
    build(1, 0, n - 1);
    // update(1, 0, n-1, idx, val);
    // query(1, 0, n-1, l, r);
}

각 연산의 호출은 build(1, 0, n-1)처럼 루트(1번)에서 시작합니다.

최솟값 트리로 바꾸기

연산을 합에서 최솟값으로 바꾸려면 결합 연산 과 항등원 만 바꿉니다.

seg[node] = ... 부분과 안 겹침 시 반환값만 교체하면 됩니다.

파이썬 (반복형, 합)

재귀가 느린 파이썬은 흔히 반복형(iterative) 세그를 씁니다.

class SegTree:
    def __init__(self, data):
        self.n = len(data)
        self.t = [0] * (2 * self.n)
        self.t[self.n:] = data                # 리프
        for i in range(self.n - 1, 0, -1):    # 내부 노드
            self.t[i] = self.t[2 * i] + self.t[2 * i + 1]

    def update(self, i, val):                 # 0-based
        i += self.n
        self.t[i] = val
        i >>= 1
        while i:
            self.t[i] = self.t[2 * i] + self.t[2 * i + 1]
            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.t[l]; l += 1
            if r & 1: r -= 1; res += self.t[r]
            l >>= 1; r >>= 1
        return res

반복형은 [l, r) 반열림 구간을 쓴다는 점에 주의하세요.

흔한 함정

• 배열 크기 — 재귀형은 4 * n을 확보해야 안전합니다. \(2N\)만 잡으면
  넘칠 수 있습니다.
• 항등원 — 안 겹침일 때 반환값이 연산의 항등원이어야 합니다(합 0, min은 INF).
• 0/1-based, 구간 표기 — 재귀형은 보통 [s, e] 닫힘, 반복형은 [l, r)
  반열림. 섞으면 off-by-one.
• 갱신 후 부모 재계산 누락 — 리프만 바꾸고 위로 안 올리면 질의가 틀립니다.
• 자료형 — 합은 쉽게 커지니 long long.

응용 패턴

• 구간 합/최값/GCD + 점 갱신 — 기본형.
• 구간 갱신 + 구간 질의 — 느리게 갱신되는 세그(lazy)로 확장(상위 단원).
• 카운팅/순위 — 값을 인덱스로 둔 세그로 "X 이하 개수", k번째 수.
• 2차원/머지 소트 트리 — 노드에 추가 자료구조를 얹는 변형.

"구간을 \(O(\log N)\)개 노드로 분해한다"는 한 가지 발상이 점 갱신과 구간 질의를
동시에 빠르게 만든다는 점이 핵심입니다. 결합 연산만 바꾸면 폭넓게 재사용됩니다.

출제 신호

• "구간 합/최솟값/최댓값/곱을 구하라" + "중간에 값이 바뀐다" +
  \(N, Q \le 10^5{\sim}10^6\) — 이 세 가지가 모두 있으면 세그먼트 트리입니다.
• 갱신이 없으면 누적 합(합)이나 희소 배열(최솟값)로 충분합니다 —
  굳이 세그트리를 꺼내지 마세요. 갱신 유무가 분기점입니다.
• 변장 신호: "자기보다 왼쪽에 있는 더 큰 수의 개수"(값 인덱스 트리),
  "\(k\)번째 수 찾기"(트리 위 이분 탐색), 스위치 켜고 끄기
• 합/덧셈 갱신만이면 코드가 더 짧은 펜윅 트리(BIT) 도 같은 신호의
  대안입니다. 최솟값·복잡한 병합은 세그먼트 트리로.

풀이 결정 절차

1. 병합 연산을 확정합니다 — 합, min, max, gcd처럼 결합법칙이 성립해야
   합니다. 항등원(합 0, min은 \(+\infty\))도 같이 적습니다.
2. 갱신이 점인지 구간인지 — 구간 갱신 + 구간 질의면 게으른 전파
   (상위 단원)가 필요합니다. 점 갱신이면 기본형으로 충분합니다.
3. 좌표(값) 범위가 \(10^9\)급인데 트리를 값 축에 세워야 하면 좌표 압축부터.
4. 복잡도 검산 — \(O((N + Q) \log N)\). 합이라면 long long
   (\(10^5\)개 \(\times\) \(10^9\) = \(10^{14}\))이 필수인지 확인합니다.

자주 하는 실수

인덱스 규약 혼선이 버그의 근원입니다. 하나의 규약을 정해 몸에 새기세요.
추천 규약: 트리는 1번 루트, 배열 크기 \(4N\), 구간은 닫힌 구간 \([l, r]\).

ll tree[4 * MAXN];                       // 4N — 2N 으로 줄이면 범위 초과

void update(int node, int s, int e, int idx, ll val) {
    if (idx < s || e < idx) return;
    if (s == e) { tree[node] = val; return; }
    int mid = (s + e) / 2;
    update(node * 2, s, mid, idx, val);
    update(node * 2 + 1, mid + 1, e, idx, val);
    tree[node] = tree[node * 2] + tree[node * 2 + 1];   // 병합 갱신을 잊지 말 것
}

ll query(int node, int s, int e, int l, int r) {
    if (r < s || e < l) return 0;        // 항등원 — min 트리면 INF
    if (l <= s && e <= r) return tree[node];
    int mid = (s + e) / 2;
    return query(node * 2, s, mid, l, r)
         + query(node * 2 + 1, mid + 1, e, l, r);
}

• 트리 크기를 \(2N\)으로 — \(N\)이 2의 거듭제곱이 아니면 재귀형은 \(4N\)이
  필요합니다. 가끔만 터지는 범위 초과(RE/WA)의 단골 원인입니다.
• 갱신 후 조상 병합 누락 — 리프만 바꾸고 올라오며 tree[node]를 다시
  계산하지 않으면 질의가 낡은 값을 봅니다.
• 항등원 실수 — min 트리의 "범위 밖" 반환을 0으로 두면 음수 없는
  배열에서 항상 0이 나옵니다. 합은 0, min은 \(+\infty\), max는 \(-\infty\).
• 질의 인자 순서 — (노드 구간 s, e)와 (질의 구간 l, r) 네 개를
  섞어 넘기는 실수. 시그니처를 항상 같은 순서로 고정하세요.
• 1-based/0-based 혼용 — 입력은 1번부터인데 트리는 0번부터 짓는 식의
  혼용. 입출력 경계에서 한 번만 변환하고 내부는 통일합니다.
• "\(k\)번째" 변형을 질의 이분 탐색으로 — 트리 밖에서 이분 탐색하면
  \(O(\log^2 N)\)이지만, 트리를 타고 내려가면 \(O(\log N)\)입니다. 왼쪽 자식
  합과 \(k\)를 비교하며 내려가는 패턴을 따로 익혀 두세요.

연습 방법

사이드바 연습 목록의 "구간 합 + 점 갱신" 표준 문제로 템플릿을 보지 않고
쓸 수 있게 만든 뒤, min/max 트리(항등원 교체), 좌표 압축이 필요한 카운팅
문제, \(k\)번째 찾기 순으로 확장하세요. 같은 문제를 펜윅 트리로도 풀어 코드
길이와 속도를 비교해 보면 도구 선택 감각이 생깁니다. 태그된 문제
3문제 이상 해결 시 마스터 처리되어 레이팅 CLASS 보너스에 반영됩니다.