1. 세그먼트 트리란?
배열이 주어졌을 때 구간 쿼리와 점 업데이트를 모두 O(log N)에 처리하는 자료구조다.
왜 필요한가?
배열 arr = [2, 5, 1, 4, 9, 3] 에서 다음 두 연산을 반복한다고 하자:
- Query: 구간
[l, r]의 합을 구하라 - Update:
arr[i]의 값을 바꿔라
| 방법 | 구간 합 쿼리 | 값 업데이트 |
|---|---|---|
| 배열 그대로 | O(N) | O(1) |
| 누적합 | O(1) | O(N) |
| 세그먼트 트리 | O(log N) | O(log N) |
쿼리가 Q번이면:
- 배열: O(NQ) → N=100,000, Q=100,000이면 10^10 → TLE
- 세그먼트 트리: O(Q log N) → 약 1,700,000 → 통과
2. 트리 구조
이진 트리 형태로, 각 노드가 특정 구간의 정보를 저장한다.
배열: [2, 5, 1, 4, 9, 3]
인덱스: 0 1 2 3 4 5
트리 구조 (구간 합):
[0~5] = 24
/ \
[0~2] = 8 [3~5] = 16
/ \ / \
[0~1]=7 [2~2]=1 [3~4]=13 [5~5]=3
/ \ / \
[0]=2 [1]=5 [3]=4 [4]=9- 리프 노드: 원래 배열의 각 원소
- 내부 노드: 자식 두 개의 합 (또는 min/max/gcd 등)
- 루트 노드: 전체 배열의 합
3. 메모리 할당
노드 번호를 1번부터 매긴다.
- 노드
i의 왼쪽 자식:2*i - 노드
i의 오른쪽 자식:2*i + 1
배열 크기가 N일 때 트리 배열은 4*N 크기로 잡으면 안전하다.
const int MAXN = 100001;
long long tree[4 * MAXN];
long long arr[MAXN];
int n, q;흔한 실수 — 루트를 0으로 두면 안 되는 이유
세그트리에서 루트는 반드시 1이다. node = 0으로 시작하면 왼쪽 자식이 0*2 = 0이라 자기 자신이 된다. 트리 구조가 무너지고, 게다가 tree[0]에 값을 덮어써서 조용히 오염된다.
build(1, 0, n-1); // 루트 = 1 ✓
update(1, 0, n-1, idx, val); // 루트 = 1 ✓
query(1, 0, n-1, l, r); // 루트 = 1 ✓첫 인자(루트=1), 둘째·셋째 인자(전체 구간 0 ~ n-1)를 셋 다 동일하게 맞추는 게 핵심이다.
4. 기본 연산 3가지
4-1. Build (트리 구축) — O(N)
배열로부터 세그먼트 트리를 처음 만든다.
// node: 현재 노드 번호
// start, end: 이 노드가 담당하는 배열 구간 [start, end]
void build(int node, int start, int end) {
if (start == end) {
// 리프 노드: 배열 값 그대로
tree[node] = arr[start];
return;
}
int mid = (start + end) / 2;
build(node * 2, start, mid); // 왼쪽 자식: [start, mid]
build(node * 2 + 1, mid + 1, end); // 오른쪽 자식: [mid+1, end]
tree[node] = tree[node * 2] + tree[node * 2 + 1]; // 합치기
}
// 호출: build(1, 0, n-1);동작 과정 (arr = [2, 5, 1, 4]):
build(1, 0, 3)
├── build(2, 0, 1)
│ ├── build(4, 0, 0) → tree[4] = 2
│ └── build(5, 1, 1) → tree[5] = 5
│ → tree[2] = 2 + 5 = 7
└── build(3, 2, 3)
├── build(6, 2, 2) → tree[6] = 1
└── build(7, 3, 3) → tree[7] = 4
→ tree[3] = 1 + 4 = 5
→ tree[1] = 7 + 5 = 124-2. Update (점 업데이트) — O(log N)
배열의 한 원소를 바꾸고, 트리를 갱신한다.
// idx: 바꿀 배열 인덱스
// val: 새로운 값
void update(int node, int start, int end, int idx, long long val) {
if (start == end) {
// 리프 노드에 도달: 값 변경
arr[idx] = val;
tree[node] = val;
return;
}
int mid = (start + end) / 2;
if (idx <= mid) {
// idx가 왼쪽 구간에 속함
update(node * 2, start, mid, idx, val);
} else {
// idx가 오른쪽 구간에 속함
update(node * 2 + 1, mid + 1, end, idx, val);
}
// 올라오면서 부모 갱신
tree[node] = tree[node * 2] + tree[node * 2 + 1];
}
// 호출: update(1, 0, n-1, idx, val);핵심: 리프까지 내려갔다가 올라오면서 경로상의 노드만 갱신한다.
트리 높이가 log N이므로 갱신되는 노드는 최대 log N개.
4-3. Query (구간 쿼리) — O(log N)
구간 [l, r]의 합을 구한다.
long long query(int node, int start, int end, int l, int r) {
// Case 1: 현재 구간이 쿼리 범위 밖 → 무시
if (r < start || end < l) {
return 0; // 합의 항등원
}
// Case 2: 현재 구간이 쿼리 범위에 완전히 포함 → 바로 반환
if (l <= start && end <= r) {
return tree[node];
}
// Case 3: 일부만 겹침 → 좌우로 나눠서 재귀
int mid = (start + end) / 2;
//long long left_sum = query(node * 2, start, mid, l, r);
//long long right_sum = query(node * 2 + 1, mid + 1, end, l, r);
return query(node * 2, start, mid, l, r) + query(node * 2 + 1, mid + 1, end, l, r);
}
// 호출: query(1, 0, n-1, l, r);3가지 Case가 핵심:
Case 1: 안 겹침 → return 0 (항등원)
[start---end]
[l------r]
Case 2: 완전 포함 → return tree[node]
[start---end]
[l------------------r]
Case 3: 일부 겹침 → 반으로 나눠서 재귀
[start------end]
[l--------r]동작 과정 (arr = [2, 10, 1, 4], query(0, 2)):
query(1, 0, 3, 0, 2)
├── query(2, 0, 1, 0, 2) → [0,1] ⊆ [0,2] → tree[2] = 12
└── query(3, 2, 3, 0, 2)
├── query(6, 2, 2, 0, 2) → [2,2] ⊆ [0,2] → tree[6] = 1
└── query(7, 3, 3, 0, 2) → 3 > 2 (범위 밖) → 0
→ 1 + 0 = 1
→ 12 + 1 = 135. 전체 코드 (구간 합)
#include <iostream>
using namespace std;
const int MAXN = 100001;
long long tree[4 * MAXN];
long long arr[MAXN];
int n, q;
void build(int node, int start, int end) {
if (start == end) { tree[node] = arr[start]; return; }
int mid = (start + end) / 2;
build(node * 2, start, mid);
build(node * 2 + 1, mid + 1, end);
tree[node] = tree[node * 2] + tree[node * 2 + 1];
}
void update(int node, int start, int end, int idx, long long val) {
if (start == end) { arr[idx] = val; tree[node] = val; return; }
int mid = (start + end) / 2;
if (idx <= mid) update(node * 2, start, mid, idx, val);
else update(node * 2 + 1, mid + 1, end, idx, val);
tree[node] = tree[node * 2] + tree[node * 2 + 1];
}
long long query(int node, int start, int end, int l, int r) {
if (r < start || end < l) return 0;
if (l <= start && end <= r) return tree[node];
int mid = (start + end) / 2;
return query(node * 2, start, mid, l, r)
+ query(node * 2 + 1, mid + 1, end, l, r);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> q;
for (int i = 0; i < n; i++) cin >> arr[i];
build(1, 0, n - 1);
while (q--) {
int type; cin >> type;
if (type == 1) {
int idx; long long val;
cin >> idx >> val;
update(1, 0, n - 1, idx, val);
} else {
int l, r; cin >> l >> r;
cout << query(1, 0, n - 1, l, r) << "\n";
}
}
}6. 응용 1: 다른 연산 (min/max/gcd/xor)
합 대신 다른 연산을 쓰려면 두 곳만 바꾸면 된다:
1. tree[node] = ... 결합 부분
2. 범위 밖에서 반환하는 항등원
| 연산 | 결합 | 항등원 (범위 밖 반환값) |
|---|---|---|
| 구간 합 | a + b | 0 |
| 구간 최솟값 | min(a, b) | LLONG_MAX |
| 구간 최댓값 | max(a, b) | LLONG_MIN |
| 구간 GCD | __gcd(a, b) | 0 |
| 구간 XOR | a ^ b | 0 |
항등원을 잘못 쓰면 조용히 오답
sum 코드를 복사해서 min 세그트리로 바꿀 때 return 0을 그대로 두면, 배열에 0보다 큰 값만 있어도 min이 0으로 오염된다. 항등원을 반드시 함께 바꿔라.
// min 세그트리 예시
tree[node] = min(tree[node*2], tree[node*2+1]); // 결합
if (r < start || end < l) return LLONG_MAX; // 항등원7. 응용 2: 노드에 여러 값 들고 다니기
세그트리 실력이 갈리는 지점. 5번급 문제의 대부분이 여기서 나온다.
핵심 아이디어: 노드를 struct로 만들어 여러 값을 동시에 저장하고,
자식 두 개를 부모로 합치는 병합 함수(merge)를 설계한다.
예시 1: 최댓값 + 그 개수
"구간 최댓값을 구하되, 그 최댓값이 몇 번 나오는지도 함께"
struct Node {
long long mx; // 구간 최댓값
int cnt; // 최댓값 등장 횟수
};
Node merge(const Node& a, const Node& b) {
if (a.mx > b.mx) return a;
if (a.mx < b.mx) return b;
return {a.mx, a.cnt + b.cnt}; // 같으면 개수 합
}
Node IDENTITY = {LLONG_MIN, 0}; // 항등원 (범위 밖)
Node tree[4 * MAXN];
Node query(int node, int s, int e, int l, int r) {
if (r < s || e < l) return IDENTITY;
if (l <= s && e <= r) return tree[node];
int m = (s + e) / 2;
return merge(query(node*2, s, m, l, r),
query(node*2+1, m+1, e, l, r));
}예시 2: 최대 부분합 (Maximum Subarray Sum) — 대표 문제
구간 [l, r]에서 연속 부분수열의 최대 합을 O(log N)에 구하기.
각 노드에 4개 값을 저장한다:
total= 구간 전체 합pre= 왼쪽 끝을 포함하는 최대 합 (prefix best)suf= 오른쪽 끝을 포함하는 최대 합 (suffix best)best= 구간 내 최대 부분합 (정답)
struct Node {
long long total, pre, suf, best;
};
Node merge(const Node& L, const Node& R) {
Node c;
c.total = L.total + R.total;
c.pre = max(L.pre, L.total + R.pre);
c.suf = max(R.suf, R.total + L.suf);
c.best = max({L.best, R.best, L.suf + R.pre});
return c;
}
Node makeLeaf(long long v) {
// 리프: 원소 하나짜리 구간
return {v, v, v, v};
}
Node IDENTITY = {0, LLONG_MIN, LLONG_MIN, LLONG_MIN};병합 논리 해석:
pre: 왼쪽에서 시작하는 최대합은 (a) 왼쪽 구간에만 걸치거나 (b) 왼쪽 구간 전체를 먹고 오른쪽 pre까지 가거나best: 정답은 (a) 왼쪽 내부, (b) 오른쪽 내부, (c) 왼쪽 suffix + 오른쪽 prefix (경계를 넘음) 중 최대
빈 부분합을 허용하는지에 따라 pre/suf/best가 음수까지 허용되는지 결정된다. 위 코드는 "최소 1개 원소를 포함하는 부분합"을 가정.
어떤 문제에서 쓰나
- 구간 내 최댓값·최솟값·최대부분합·괄호 매칭 등 "노드 간 정보 결합이 자명하지 않은" 모든 문제
- CF 380C Sereja and Brackets:
(len, unmatched_open, unmatched_close)3-tuple 결합으로 구간 내 최장 올바른 괄호 부분수열 - CF 339D Xenia and Bit Operations: 노드에
(value, level)저장, 짝수 레벨은 OR, 홀수는 XOR로 결합
8. 응용 3: 세그트리 위 이분탐색
"왼쪽부터 합이 K 이상이 되는 첫 위치"를 O(log N)에 찾을 수 있다.
// 합이 k 이상이 되는 첫 인덱스 찾기
int find_first(int node, int start, int end, long long k) {
if (start == end) return start;
int mid = (start + end) / 2;
if (tree[node * 2] >= k) {
// 왼쪽 자식의 합이 k 이상 → 왼쪽에서 찾기
return find_first(node * 2, start, mid, k);
} else {
// 왼쪽 합이 부족 → 오른쪽에서 (k - 왼쪽 합)을 찾기
return find_first(node * 2 + 1, mid + 1, end, k - tree[node * 2]);
}
}핵심: 이분탐색 O(log N)을 별도로 돌리는 것보다 O(log N)이 아니라 상수배 빠르다.
"세그트리 밖에서 이분탐색 + 안에서 쿼리 O(log²N)"으로 짠 뒤 이 방식으로 바꾸면 log가 하나 없어진다.
대표 문제:
- CF 1354D Multiset: k번째 원소 찾기 (n, q ≤ 10⁶라 log 하나 차이가 결정적)
- CF 1208D Restore Permutation
9. 응용 4: 레이지 프로파게이션 (Lazy Propagation) — 구간 add
문제
기본 세그트리는 점 업데이트만 가능. 구간 업데이트 (구간 [l, r] 전체에 값을 더하기)는 순진하게 하면 O(N log N)이 든다.
핵심 아이디어
업데이트를 나중으로 미룬다. 지금 자식까지 내려가지 않고,
"나중에 내려갈 때 이만큼 더해야 한다"는 정보를 lazy 배열에 기록한다.
long long tree[4 * MAXN];
long long lazy[4 * MAXN];propagate
자식으로 내려가기 전에, 노드에 쌓인 lazy를 자식에게 전달한다.
void propagate(int node, int start, int end) {
if (lazy[node] == 0) return;
int mid = (start + end) / 2;
int left = node * 2, right = node * 2 + 1;
tree[left] += lazy[node] * (mid - start + 1);
lazy[left] += lazy[node];
tree[right] += lazy[node] * (end - mid);
lazy[right] += lazy[node];
lazy[node] = 0;
}왜 (mid - start + 1)을 곱하나?
자식이 담당하는 구간의 원소 개수. 각 원소에 lazy[node]만큼 더하면 합은 그 곱만큼 증가.
오버플로우 주의 — 실전에서 자주 죽는 지점
tree[left] += lazy[node] * (mid - start + 1);lazy가 크고 구간이 길면 long long 곱도 넘칠 수 있다. 예: lazy ~ 10⁹, 구간 길이 10⁵ → 10¹⁴ (아직 안전) → 하지만 lazy ~ 10¹⁴이 이미 누적된 상태에서 다시 10⁵를 곱하면 10¹⁹ → 오버플로우.
곱하기 전에 피연산자 크기를 세는 습관을 들이자. 필요하면 __int128.
구간 업데이트
void range_update(int node, int start, int end, int l, int r, long long val) {
if (r < start || end < l) return;
if (l <= start && end <= r) {
tree[node] += val * (end - start + 1);
lazy[node] += val;
return;
}
propagate(node, start, end);
int mid = (start + end) / 2;
range_update(node * 2, start, mid, l, r, val);
range_update(node * 2 + 1, mid + 1, end, l, r, val);
tree[node] = tree[node * 2] + tree[node * 2 + 1];
}구간 쿼리 (레이지 버전)
long long query(int node, int start, int end, int l, int r) {
if (r < start || end < l) return 0;
if (l <= start && end <= r) return tree[node];
propagate(node, start, end); // ★ 내려가기 전에 반드시!
int mid = (start + end) / 2;
return query(node * 2, start, mid, l, r)
+ query(node * 2 + 1, mid + 1, end, l, r);
}시간복잡도 비교
| 연산 | 기본 | 레이지 |
|---|---|---|
| 점 업데이트 | O(log N) | O(log N) |
| 구간 업데이트 | O(N log N) | O(log N) |
| 구간 쿼리 | O(log N) | O(log N) |
10. 응용 5: 레이지 — assign(대입) + 두 연산 공존
Lazy의 진짜 어려움은 여기서 시작된다.
두 종류의 구간 업데이트
- add(더하기):
arr[i] += val→ lazy 누적 가능 (lazy += val) - assign(덮어쓰기):
arr[i] = val→ 누적 아님, 최신값이 이전 것을 무효화
둘이 섞이면 각 lazy를 어떻게 표현하고, 우선순위 규칙을 어떻게 유지할지가 관건이다.
표현
노드마다 두 lazy를 갖는다:
long long lazy_add[4 * MAXN]; // 더하기용
long long lazy_set[4 * MAXN]; // 덮어쓰기용
bool has_set[4 * MAXN]; // set이 걸려 있는지 (0으로 set할 수도 있으므로 값만으로 판단 불가)우선순위 규칙 (핵심)
"가장 최근 set 이후의 add만 유효"하다. 즉 set이 걸리면 그 이전 lazy는 다 무효화되고, 이후 add만 누적된다.
apply_set(v):set = v,add = 0,has_set = true,tree = v * lenapply_add(v):add += v,tree += v * len— set 여부와 무관- 주의:
has_set == true인 상태에서 새 set이 들어오면 이전 add도 무효
propagate 순서
set 먼저, add 나중이 절대 규칙이다. 반대로 하면 add를 덮어써서 잃어버린다.
void apply_set(int node, int len, long long v) {
tree[node] = v * len;
lazy_set[node] = v;
has_set[node] = true;
lazy_add[node] = 0; // set이 들어오면 이전 add 무효
}
void apply_add(int node, int len, long long v) {
tree[node] += v * len;
if (has_set[node]) lazy_set[node] += v; // set 후 add는 set 값에 합쳐도 됨
else lazy_add[node] += v;
}
void propagate(int node, int start, int end) {
if (start == end) return;
int mid = (start + end) / 2;
int L = node*2, R = node*2+1;
int lenL = mid - start + 1, lenR = end - mid;
if (has_set[node]) { // ★ set 먼저
apply_set(L, lenL, lazy_set[node]);
apply_set(R, lenR, lazy_set[node]);
has_set[node] = false;
lazy_set[node] = 0;
}
if (lazy_add[node] != 0) { // ★ add 나중
apply_add(L, lenL, lazy_add[node]);
apply_add(R, lenR, lazy_add[node]);
lazy_add[node] = 0;
}
}이 패턴을 한 번만 정확히 몸에 익혀두면 파생 문제에 그대로 재사용된다. ITMO Academy Part 2에서 반복해서 나온다.
11. 응용 6: 좌표 압축 + 세그트리
값의 범위가 10⁹처럼 클 때, 실제로 등장하는 값만 압축해서 세그트리를 만든다.
vector<int> vals(arr, arr + n);
sort(vals.begin(), vals.end());
vals.erase(unique(vals.begin(), vals.end()), vals.end());
int compressed = lower_bound(vals.begin(), vals.end(), x) - vals.begin();역순쌍 세기, LIS 등에서 필수.
12. 응용 7: 머지 소트 트리
각 노드에 정렬된 배열을 저장. 구간 내 K보다 작은 원소 개수 등을 O(log² N)에 구할 수 있다.
vector<int> seg[4 * MAXN];
void build(int node, int start, int end) {
if (start == end) { seg[node].push_back(arr[start]); return; }
int mid = (start + end) / 2;
build(node * 2, start, mid);
build(node * 2 + 1, mid + 1, end);
merge(seg[node * 2].begin(), seg[node * 2].end(),
seg[node * 2 + 1].begin(), seg[node * 2 + 1].end(),
back_inserter(seg[node]));
}
int query(int node, int start, int end, int l, int r, int K) {
if (r < start || end < l) return 0;
if (l <= start && end <= r) {
return lower_bound(seg[node].begin(), seg[node].end(), K)
- seg[node].begin();
}
int mid = (start + end) / 2;
return query(node * 2, start, mid, l, r, K)
+ query(node * 2 + 1, mid + 1, end, l, r, K);
}메모리 O(N log N), 쿼리 O(log² N).
13. 비재귀 세그먼트 트리 (Iterative)
재귀보다 빠르고 코드가 짧다. 실전 속도가 중요할 때.
int sz;
long long tree[2 * MAXN];
void build() {
sz = 1;
while (sz < n) sz *= 2;
for (int i = 0; i < n; i++) tree[sz + i] = arr[i];
for (int i = sz - 1; i >= 1; i--)
tree[i] = tree[2 * i] + tree[2 * i + 1];
}
void update(int idx, long long val) {
idx += sz;
tree[idx] = val;
for (idx /= 2; idx >= 1; idx /= 2)
tree[idx] = tree[2 * idx] + tree[2 * idx + 1];
}
// [l, r] 구간 합 (0-indexed)
long long query(int l, int r) {
long long res = 0;
for (l += sz, r += sz + 1; l < r; l /= 2, r /= 2) {
if (l & 1) res += tree[l++];
if (r & 1) res += tree[--r];
}
return res;
}비재귀의 함정
함정 1 — 비가환 연산에선 좌·우를 따로 모아야 한다.
sum, xor, min, max처럼 교환법칙이 성립하는 연산은 위 코드가 그냥 된다. 하지만 문자열 연결·행렬 곱처럼 순서가 의미 있는 연산은, res에 아무 순서로 붙이면 답이 뒤섞인다. 왼쪽에서 온 것과 오른쪽에서 온 것을 별도로 모은 뒤 마지막에 resL ⊕ resR로 합쳐야 한다.
함정 2 — 반열림 구간 [l, r).
위 코드는 r += sz + 1로 exclusive처럼 다룬다. sum/xor 문제에서 이 규약을 이해하지 못하고 다른 연산으로 복붙하면 off-by-one으로 조용히 틀린다.
함정 3 — Lazy 구현이 복잡.
이론은 되지만 코드가 길어져서, 처음엔 재귀 세그트리로 lazy를 익히고 나중에 옮기는 걸 권한다. Efficient and easy segment trees 참고.
장점: 상수 작음, 캐시 효율 좋음, 코드 짧음
단점: lazy 복잡, 비가환 연산 주의
14. 정리
| 유형 | 시간복잡도 | 언제 쓰나 |
|---|---|---|
| 기본 세그트리 | Build O(N), Q/U O(log N) | 점 업데이트 + 구간 쿼리 |
| Struct 노드 | 위와 동일 | 최대 부분합, 괄호 매칭, min+개수 등 |
| 레이지 (add) | 모든 연산 O(log N) | 구간 add + 구간 쿼리 |
| 레이지 (set+add) | O(log N) | 두 종류 구간 업데이트 공존 |
| 세그트리 위 이분탐색 | O(log N) | K번째 원소, 첫 위치 찾기 |
| 좌표 압축 | O(N log N) | 값 범위가 클 때 |
| 머지 소트 트리 | O(log² N) | 구간 내 K보다 작은 원소 수 |
| 비재귀 | O(log N), 상수 작음 | 속도 중요, lazy 없음 |
15. 외부 자료
- ITMO Academy 세그트리 코스 (Codeforces EDU) — 강의·문제·채점 통합, 대회식 자료로 가장 정리 잘됨: https://codeforces.com/edu/course/2
- Efficient and easy segment trees by Al.Cash — iterative 세그트리 정석: https://codeforces.com/blog/entry/18051
- cp-algorithms 세그트리: https://cp-algorithms.com/data_structures/segment_tree.html
- Algorithm Gym :: Everything About Segment Trees: https://codeforces.com/blog/entry/15890
