C++ 트리 알고리즘 완벽 가이드 | 세그먼트 트리·펜윅 트리·트라이 [실전]
![C++ 트리 알고리즘 완벽 가이드 | 세그먼트 트리·펜윅 트리·트라이 [실전]](/og/s/cpp-series-54-6-tree-algorithms.webp)
이 글의 핵심
C++ 구간 쿼리·누적합·자동완성을 위한 고급 트리. 세그먼트 트리 구간 쿼리, 펜윅 트리 누적합, 트라이 문자열 검색. 문제 시나리오, 완전한 예제, 흔한 실수, 성능 팁, 프로덕션 패턴.
들어가며: “구간 합 쿼리가 O(n)이라 느려요”
실제 겪는 문제 시나리오
배열에서 구간 [L, R]의 합을 10만 번 쿼리할 때, 매번 O(n)으로 순회하면 시간 초과가 납니다. 비유하면 “매번 책 전체를 읽는 것”과 “목차에서 필요한 페이지만 찾는 것”의 차이입니다.
flowchart TD
subgraph wrong["❌ 단순 반복 O(n) per query"]
W1[쿼리 10만 번] --> W2[매번 [L,R] 순회]
W2 --> W3[n=10만 × 10만 = 100억]
W3 --> W4[시간 초과]
end
subgraph right["✅ 세그먼트/펜윅 트리 O(log n) per query"]
R1[쿼리 10만 번] --> R2[트리에서 구간 합 O(log n)]
R2 --> R3[10만 × log(10만) ≈ 170만]
R3 --> R4[밀리초 단위]
end
이 글에서는 실제로 겪는 문제 시나리오부터 시작해, 세그먼트 트리·펜윅 트리·트라이의 완전한 C++ 구현, 자주 하는 실수, 성능 최적화 팁, 프로덕션 패턴까지 단계별로 다룹니다.
이 글을 읽으면:
- 구간 쿼리·누적합·접두사 검색 문제에 맞는 자료구조를 선택할 수 있습니다.
- 세그먼트 트리, 펜윅 트리, 트라이를 직접 구현할 수 있습니다.
- 흔한 실수를 피하고 성능을 최적화할 수 있습니다.
요구 환경: C++17 이상
목차
1. 문제 시나리오
시나리오 1: 구간 합/최솟값 쿼리 + 원소 업데이트
상황: 실시간 주가 데이터에서 “3일~7일 구간의 최저가”를 1초에 수천 번 조회하고, 가격이 바뀔 때마다 업데이트해야 합니다.
잘못된 접근:
// ❌ 매 쿼리마다 O(n) 순회
std::vector<int> prices = {100, 95, 102, 98, 105, 103, 107};
int query_min(int L, int R) {
int mn = INT_MAX;
for (int i = L; i <= R; ++i) mn = std::min(mn, prices[i]);
return mn;
}
// 쿼리 10만 번 × n=10만 → 100억 연산 → 시간 초과해결: 세그먼트 트리 — 구간 쿼리 O(log n), 단일 원소 업데이트 O(log n).
시나리오 2: 누적합 + 빈번한 업데이트
상황: 주문 시스템에서 “1번~k번 주문의 총 금액”을 자주 조회하고, 새 주문이 들어올 때마다 배열이 갱신됩니다.
잘못된 접근:
// ❌ prefix sum만 쓰면 업데이트 시 O(n) 재계산
std::vector<long long> prefix;
void update(int i, int delta) {
arr[i] += delta;
for (int j = i; j < n; ++j) prefix[j] += delta; // O(n)
}해결: 펜윅 트리(BIT) — 누적합 쿼리 O(log n), 단일 업데이트 O(log n). 구현이 세그먼트 트리보다 간단합니다.
시나리오 3: 접두사 검색 (자동완성)
상황: 검색창에 “app”을 입력하면 “apple”, “application”, “apply” 등을 O(접두사 길이)에 제안해야 합니다.
잘못된 접근:
// ❌ std::map - 접두사 검색 O(n)
std::map<std::string, int> words;
for (auto it = words.lower_bound("app"); it != words.end(); ++it) {
if (it->first.substr(0, 3) != "app") break;
suggest(it->first); // 전체 키 순회 가능
}해결: 트라이(Trie) — 삽입/검색 O(m), 접두사 검색 O(m). m은 문자열 길이.
시나리오 4: 구간에 대한 복합 연산
상황: 구간 [L,R]에서 “최대값 - 최소값” 또는 “XOR 합”을 구해야 합니다.
해결: 세그먼트 트리의 병합 함수를 해당 연산으로 바꾸면 됩니다. (합 → 최대/최소/XOR 등)
시나리오 5: k번째 원소 찾기 (순위 쿼리)
상황: 게임 순위표에서 “상위 10%에 속하는 사용자 수” 또는 “k번째로 큰 점수”를 실시간으로 찾아야 합니다. 점수가 자주 업데이트됩니다.
잘못된 접근:
// ❌ 매번 정렬하면 O(n log n) × 쿼리 수
std::vector<int> scores;
int kth_largest(int k) {
auto sorted = scores;
std::sort(sorted.begin(), sorted.end(), std::greater<int>());
return sorted[k - 1];
}해결: 세그먼트 트리 또는 펜윅 트리로 값의 범위를 인덱스로 삼아 구간 합을 유지. 이진 탐색으로 “합이 k 이상인 최소 인덱스”를 찾으면 k번째 원소를 O(log² n)에 구할 수 있습니다.
시나리오 6: 동적 구간 쿼리 (LeetCode 307 스타일)
상황: 배열 nums가 주어지고, 다음 두 연산을 반복합니다.
update(index, val):nums[index]를val로 변경sumRange(left, right):nums[left] + ... + nums[right]반환
잘못된 접근:
// ❌ prefix sum만 쓰면 update 시 O(n) 재계산
// ❌ 매 쿼리마다 for 루프 → O(n) per query해결: 세그먼트 트리 또는 펜윅 트리로 둘 다 O(log n)에 처리할 수 있습니다.
알고리즘 선택 가이드
| 문제 유형 | 추천 자료구조 | 쿼리 | 업데이트 | 비고 |
|---|---|---|---|---|
| 구간 합 | 펜윅 트리 | O(log n) | O(log n) | 구현 간단 |
| 구간 최소/최대 | 세그먼트 트리 | O(log n) | O(log n) | 펜윅은 비적합 |
| 구간 XOR, GCD | 세그먼트 트리 | O(log n) | O(log n) | 역원 필요 |
| 접두사 검색 | 트라이 | O(m) | O(m) | m=문자열 길이 |
| 순위 쿼리 (k번째) | 세그먼트 트리 | O(log n) | O(log n) | 이진 탐색 결합 |
2. 세그먼트 트리 완전 구현
2.1 핵심 아이디어
세그먼트 트리는 이진 트리로, 각 노드가 배열의 한 구간을 담당합니다. 루트는 [0, n-1], 왼쪽 자식은 [0, mid], 오른쪽 자식은 [mid+1, n-1]을 담당합니다.
flowchart TD
subgraph tree[세그먼트 트리 구조]
R["[0,6] 합"]
R --> L[[0,2]]
R --> RR[[3,6]]
L --> LL[[0,1]]
L --> LR[[2,2]]
RR --> RL[[3,4]]
RR --> RRR[[5,6]]
end
시간 복잡도: 구간 쿼리 O(log n), 단일 업데이트 O(log n). 공간: O(n) (배열 4n 크기로 충분).
2.2 구간 합 세그먼트 트리
#include <vector>
#include <algorithm>
#include <cassert>
// 구간 합 세그먼트 트리
// - build: O(n)
// - query: O(log n)
// - update: O(log n)
class SegmentTree {
std::vector<long long> tree_;
int n_;
// [l, r]은 현재 노드가 담당하는 구간, [ql, qr]은 쿼리 구간
long long queryImpl(int node, int l, int r, int ql, int qr) {
if (qr < l || r < ql) return 0; // 구간 겹침 없음
if (ql <= l && r <= qr) return tree_[node]; // 완전 포함
int mid = (l + r) / 2;
return queryImpl(2 * node, l, mid, ql, qr)
+ queryImpl(2 * node + 1, mid + 1, r, ql, qr);
}
void updateImpl(int node, int l, int r, int idx, long long delta) {
if (idx < l || r < idx) return;
if (l == r) {
tree_[node] += delta;
return;
}
int mid = (l + r) / 2;
updateImpl(2 * node, l, mid, idx, delta);
updateImpl(2 * node + 1, mid + 1, r, idx, delta);
tree_[node] = tree_[2 * node] + tree_[2 * node + 1];
}
public:
explicit SegmentTree(const std::vector<long long>& arr) : n_(static_cast<int>(arr.size())) {
tree_.resize(4 * n_);
build(1, 0, n_ - 1, arr);
}
void build(int node, int l, int r, const std::vector<long long>& arr) {
if (l == r) {
tree_[node] = arr[l];
return;
}
int mid = (l + r) / 2;
build(2 * node, l, mid, arr);
build(2 * node + 1, mid + 1, r, arr);
tree_[node] = tree_[2 * node] + tree_[2 * node + 1];
}
long long query(int ql, int qr) {
assert(0 <= ql && ql <= qr && qr < n_);
return queryImpl(1, 0, n_ - 1, ql, qr);
}
void update(int idx, long long delta) {
assert(0 <= idx && idx < n_);
updateImpl(1, 0, n_ - 1, idx, delta);
}
};2.3 구간 최소값 세그먼트 트리 (RMQ)
#include <vector>
#include <algorithm>
#include <climits>
// Range Minimum Query 세그먼트 트리
class SegmentTreeMin {
std::vector<int> tree_;
int n_;
static constexpr int INF = INT_MAX;
int queryImpl(int node, int l, int r, int ql, int qr) {
if (qr < l || r < ql) return INF;
if (ql <= l && r <= qr) return tree_[node];
int mid = (l + r) / 2;
return std::min(
queryImpl(2 * node, l, mid, ql, qr),
queryImpl(2 * node + 1, mid + 1, r, ql, qr)
);
}
void updateImpl(int node, int l, int r, int idx, int val) {
if (idx < l || r < idx) return;
if (l == r) {
tree_[node] = val;
return;
}
int mid = (l + r) / 2;
updateImpl(2 * node, l, mid, idx, val);
updateImpl(2 * node + 1, mid + 1, r, idx, val);
tree_[node] = std::min(tree_[2 * node], tree_[2 * node + 1]);
}
public:
explicit SegmentTreeMin(const std::vector<int>& arr) : n_(static_cast<int>(arr.size())) {
tree_.resize(4 * n_, INF);
build(1, 0, n_ - 1, arr);
}
void build(int node, int l, int r, const std::vector<int>& arr) {
if (l == r) {
tree_[node] = arr[l];
return;
}
int mid = (l + r) / 2;
build(2 * node, l, mid, arr);
build(2 * node + 1, mid + 1, r, arr);
tree_[node] = std::min(tree_[2 * node], tree_[2 * node + 1]);
}
int query(int ql, int qr) { return queryImpl(1, 0, n_ - 1, ql, qr); }
void update(int idx, int val) { updateImpl(1, 0, n_ - 1, idx, val); }
};2.4 사용 예시
#include <iostream>
int main() {
std::vector<long long> arr = {1, 3, 5, 7, 9, 11};
SegmentTree st(arr);
std::cout << st.query(1, 3) << "\n"; // 3+5+7 = 15
st.update(2, 10); // arr[2] += 10 → 5→15
std::cout << st.query(1, 3) << "\n"; // 3+15+7 = 25
std::vector<int> mins = {2, 5, 1, 8, 3, 9};
SegmentTreeMin stMin(mins);
std::cout << stMin.query(0, 2) << "\n"; // min(2,5,1) = 1
return 0;
}2.5 통합 예제: 구간 쿼리 + 점 업데이트 (LeetCode 307 스타일)
문제: NumArray 클래스가 update(index, val)과 sumRange(left, right)를 O(log n)에 지원해야 합니다.
// LeetCode 307: Range Sum Query - Mutable
class NumArray {
std::vector<long long> tree_;
int n_;
std::vector<int> nums_;
void build(int node, int l, int r) {
if (l == r) { tree_[node] = nums_[l]; return; }
int mid = (l + r) / 2;
build(2*node, l, mid);
build(2*node+1, mid+1, r);
tree_[node] = tree_[2*node] + tree_[2*node+1];
}
void updateImpl(int node, int l, int r, int idx, long long delta) {
if (idx < l || r < idx) return;
if (l == r) { tree_[node] += delta; return; }
int mid = (l + r) / 2;
updateImpl(2*node, l, mid, idx, delta);
updateImpl(2*node+1, mid+1, r, idx, delta);
tree_[node] = tree_[2*node] + tree_[2*node+1];
}
long long queryImpl(int node, int l, int r, int ql, int qr) {
if (qr < l || r < ql) return 0;
if (ql <= l && r <= qr) return tree_[node];
int mid = (l + r) / 2;
return queryImpl(2*node, l, mid, ql, qr)
+ queryImpl(2*node+1, mid+1, r, ql, qr);
}
public:
explicit NumArray(const std::vector<int>& nums)
: n_(static_cast<int>(nums.size())), nums_(nums) {
tree_.resize(4 * n_);
build(1, 0, n_ - 1);
}
void update(int index, int val) {
long long delta = val - nums_[index];
nums_[index] = val;
updateImpl(1, 0, n_ - 1, index, delta);
}
long long sumRange(int left, int right) {
return queryImpl(1, 0, n_ - 1, left, right);
}
};
// 사용: NumArray na({1,3,5}); na.sumRange(0,2)==9; na.update(1,2); na.sumRange(0,2)==8;펜윅 트리로 동일 문제 해결:
class NumArrayFenwick {
FenwickTree ft_;
std::vector<int> nums_;
public:
explicit NumArrayFenwick(const std::vector<int>& nums)
: ft_(static_cast<int>(nums.size())), nums_(nums) {
for (int i = 0; i < static_cast<int>(nums.size()); ++i) ft_.add(i + 1, nums[i]);
}
void update(int index, int val) {
ft_.add(index + 1, val - nums_[index]);
nums_[index] = val;
}
long long sumRange(int left, int right) { return ft_.rangeSum(left + 1, right + 1); }
};3. 펜윅 트리 완전 구현
3.1 핵심 아이디어
펜윅 트리(Binary Indexed Tree, BIT)는 비트 연산을 활용해 누적합을 O(log n)에 구합니다. 세그먼트 트리보다 코드가 짧고, 캐시 친화적입니다.
핵심: i의 이진 표현에서 마지막 1의 위치를 i & -i로 구합니다. i번 노드는 [i - (i&-i) + 1, i] 구간의 합을 담습니다.
flowchart LR
subgraph bit[펜윅 트리 인덱스]
B1["1: [1,1]"]
B2["2: [1,2]"]
B3["3: [3,3]"]
B4["4: [1,4]"]
B5["5: [5,5]"]
B6["6: [5,6]"]
end
3.2 펜윅 트리 구현
#include <vector>
#include <cassert>
// 펜윅 트리 (1-indexed)
// - prefix sum [1..i]를 O(log n)에 구함
// - update(i, delta): i번 원소에 delta 더함
class FenwickTree {
std::vector<long long> tree_;
int n_;
public:
explicit FenwickTree(int n) : n_(n), tree_(n + 1, 0) {}
// i번째(1-indexed) 원소에 delta를 더함
void add(int i, long long delta) {
assert(1 <= i && i <= n_);
for (; i <= n_; i += (i & -i)) {
tree_[i] += delta;
}
}
// [1, i] 구간 합 (prefix sum)
long long prefixSum(int i) {
assert(0 <= i && i <= n_);
long long sum = 0;
for (; i > 0; i -= (i & -i)) {
sum += tree_[i];
}
return sum;
}
// [L, R] 구간 합 (1-indexed)
long long rangeSum(int L, int R) {
assert(1 <= L && L <= R && R <= n_);
return prefixSum(R) - prefixSum(L - 1);
}
// 초기 배열로 구성 (선택적)
void init(const std::vector<long long>& arr) {
for (int i = 0; i < static_cast<int>(arr.size()) && i + 1 <= n_; ++i) {
add(i + 1, arr[i]);
}
}
};3.3 펜윅 트리 사용 예시
int main() {
FenwickTree ft(6);
ft.add(1, 1);
ft.add(2, 3);
ft.add(3, 5);
ft.add(4, 7);
ft.add(5, 9);
ft.add(6, 11);
std::cout << ft.rangeSum(2, 4) << "\n"; // 3+5+7 = 15
ft.add(3, 10); // 3번 원소에 10 추가
std::cout << ft.rangeSum(2, 4) << "\n"; // 3+15+7 = 25
return 0;
}3.4 펜윅 vs 세그먼트 트리
| 항목 | 펜윅 트리 | 세그먼트 트리 |
|---|---|---|
| 구현 난이도 | 간단 | 상대적으로 복잡 |
| 공간 | O(n) | O(4n) |
| 구간 합 | O(log n) | O(log n) |
| 구간 최소/최대 | ❌ 부적합 | ✅ 지원 |
| 역원 | 합: 뺄셈 | 필요 시 역원 정의 |
| 캐시 | 더 친화적 | 상대적으로 불리 |
펜윅 사용 조건: 연산이 역원을 가져야 합니다 (합→뺄셈, XOR→XOR). 최소/최대는 역원이 없어 펜윅으로 구간 쿼리가 어렵습니다.
4. 트라이 완전 구현
4.1 핵심 아이디어
트라이는 문자별로 자식을 따라가는 트리입니다. “apple”을 저장하면 a→p→p→l→e 경로가 생기고, 각 노드에 “단어 끝” 표시를 둡니다.
flowchart TD R[(루트)] --> A[a] A --> P1[p] P1 --> P2[p] P2 --> L[l] L --> E[e*] A --> N[n] N --> T[t*]
4.2 트라이 구현 (영소문자)
#include <string>
#include <array>
#include <vector>
#include <memory>
class Trie {
struct Node {
std::array<std::unique_ptr<Node>, 26> children{};
bool is_end = false;
};
std::unique_ptr<Node> root_ = std::make_unique<Node>();
static int index(char c) {
if (c < 'a' || c > 'z') return -1;
return c - 'a';
}
public:
void insert(const std::string& word) {
Node* cur = root_.get();
for (char c : word) {
int i = index(c);
if (i < 0) return;
if (!cur->children[i]) {
cur->children[i] = std::make_unique<Node>();
}
cur = cur->children[i].get();
}
cur->is_end = true;
}
bool search(const std::string& word) {
Node* cur = root_.get();
for (char c : word) {
int i = index(c);
if (i < 0 || !cur->children[i]) return false;
cur = cur->children[i].get();
}
return cur->is_end;
}
bool startsWith(const std::string& prefix) {
Node* cur = root_.get();
for (char c : prefix) {
int i = index(c);
if (i < 0 || !cur->children[i]) return false;
cur = cur->children[i].get();
}
return true;
}
// 접두사 prefix로 시작하는 모든 단어 수집
std::vector<std::string> wordsWithPrefix(const std::string& prefix) {
std::vector<std::string> result;
Node* cur = root_.get();
for (char c : prefix) {
int i = index(c);
if (i < 0 || !cur->children[i]) return result;
cur = cur->children[i].get();
}
collect(cur, prefix, result);
return result;
}
private:
void collect(Node* node, const std::string& prefix, std::vector<std::string>& out) {
if (!node) return;
if (node->is_end) out.push_back(prefix);
for (int i = 0; i < 26; ++i) {
if (node->children[i]) {
collect(node->children[i].get(), prefix + static_cast<char>('a' + i), out);
}
}
}
};4.3 트라이 사용 예시 (자동완성)
#include <iostream>
int main() {
Trie trie;
trie.insert("apple");
trie.insert("application");
trie.insert("apply");
trie.insert("banana");
std::cout << trie.search("apple") << "\n"; // 1 (true)
std::cout << trie.search("app") << "\n"; // 0 (false)
std::cout << trie.startsWith("app") << "\n"; // 1 (true)
auto suggestions = trie.wordsWithPrefix("app");
for (const auto& w : suggestions) {
std::cout << w << " "; // apple application apply
}
return 0;
}4.4 압축 트라이 (Patricia Trie) 개요
자식이 하나만 있는 노드를 합쳐 공간을 절약하는 변형입니다. 실무에서는 대용량 문자열 집합에 유용합니다.
// 압축 트라이: 연속된 단일 자식 경로를 하나의 "간선 레이블"로 압축
// 예: "application" → "app" + "lication" (app 다음에 여러 분기)
// 구현 복잡도가 높아, 기본 트라이로 충분한 경우가 많음5. 자주 발생하는 에러와 해결법
문제 1: 세그먼트 트리 인덱스 0 vs 1
증상: 쿼리 결과가 잘못되거나 세그먼트 폴트가 발생합니다.
원인: 세그먼트 트리는 보통 0-indexed로 구현하는데, 문제에서 1-indexed를 요구할 수 있습니다.
// ❌ 1-indexed 문제를 0-indexed로 그대로 쿼리
int ans = st.query(L, R); // L,R이 1..n이면 범위 초과
// ✅ 1-indexed 입력을 0-indexed로 변환
int ans = st.query(L - 1, R - 1);문제 2: 펜윅 트리 0-indexed vs 1-indexed 혼동
증상: add(0, x) 호출 시 무한 루프 또는 잘못된 결과.
원인: 펜윅 트리는 1-indexed가 표준입니다. i += (i & -i)에서 i=0이면 진행이 안 됩니다.
// ❌ 0-indexed 배열을 그대로 add(0, x)
ft.add(0, arr[0]); // 0은 사용하지 않음!
// ✅ 1-indexed로 변환
for (int i = 0; i < n; ++i) ft.add(i + 1, arr[i]);문제 3: 세그먼트 트리 배열 크기 부족
증상: 런타임에 인덱스 초과 또는 쓰레기 값.
원인: tree 크기가 4*n 미만이면 재귀 깊이에 따라 접근이 넘칠 수 있습니다.
// ❌ n만 할당
tree_.resize(n_);
// ✅ 4*n 이상 할당 (안전)
tree_.resize(4 * n_);문제 4: 트라이에서 메모리 누수
증상: 대량 문자열 삽입 후 메모리 사용량이 계속 증가합니다.
원인: delete를 호출하지 않거나, unique_ptr 없이 raw 포인터만 사용할 때.
// ❌ raw 포인터, 수동 delete 누락
Node* child = new Node();
cur->children[i] = child; // 나중에 delete 안 함
// ✅ unique_ptr 사용
cur->children[i] = std::make_unique<Node>();문제 5: 구간 [L,R] 경계 처리
증상: query(L, R)에서 L > R일 때 잘못된 동작.
원인: L > R이면 빈 구간인데, 구현에 따라 0을 반환해야 합니다.
// ✅ 쿼리 전 검증
long long query(int ql, int qr) {
if (ql > qr) return 0; // 빈 구간
return queryImpl(1, 0, n_ - 1, ql, qr);
}문제 6: 펜윅 트리에서 구간 최소/최대 시도
증상: 구간 최소값을 펜윅으로 구현하려다 실패합니다.
원인: 최소/최대 연산은 역원이 없습니다. min(a,b)에서 a를 알 수 없으면 b만으로 복원 불가.
// ❌ 펜윅으로 RMQ 시도 - 불가능
// prefixMin(i) = min(arr[1], ..., arr[i])는 가능하지만
// rangeMin(L, R)은 prefixMin만으로 불가능
// ✅ 구간 최소/최대는 세그먼트 트리 사용
SegmentTreeMin stMin(arr);
int mn = stMin.query(L, R);문제 7: 합 쿼리에서 int 오버플로우
증상: 구간 합이 예상과 다르거나 음수가 나옵니다.
원인: int 범위(약 ±21억)를 넘는 누적합. n=10만, 원소 최대 10만이면 합이 100억을 넘을 수 있습니다.
// ❌ int 사용 - 오버플로우
std::vector<int> tree_;
long long query(...) { return tree_[node]; } // 반환형만 long long
// ✅ tree_와 반환형 모두 long long
std::vector<long long> tree_;
long long query(...) { return tree_[node]; }문제 8: lazy propagation에서 전파 순서 오류
증상: 구간 업데이트 후 쿼리 결과가 잘못됩니다.
원인: 자식에게 lazy를 전파하기 전에 현재 노드 값을 갱신해야 합니다. 순서가 바뀌면 자식의 lazy가 덮어쓰여질 수 있습니다.
// ✅ 올바른 순서: 1) 현재 노드에 lazy 반영 2) 자식에게 전파 3) lazy 초기화
if (lazy[node] != 0) {
tree_[node] += lazy[node] * (r - l + 1);
if (l != r) {
lazy[2*node] += lazy[node];
lazy[2*node+1] += lazy[node];
}
lazy[node] = 0;
}6. 베스트 프랙티스
| 항목 | 권장 사항 |
|---|---|
| 인덱스 규칙 | 코드 상단에 // SegmentTree: 0-indexed, // FenwickTree: 1-indexed 명시 |
| 검증 | assert(0 <= ql && ql <= qr && qr < n_)로 디버그 빌드에서 검증 |
| 항등원 | 합: 0, 최소: INF, 최대: INT_MIN, XOR: 0, 곱: 1 |
| 트라이 문자 | index(c)에서 영소문자 외 -1 반환, early return |
| 대규모 n | n≥100만이면 재귀 대신 반복문(Bottom-Up) 세그먼트 트리 고려 |
7. 성능 최적화 팁
1. 세그먼트 트리 반복문 구현 (스택 오버플로우 방지)
재귀 대신 반복문으로 구현하면 스택 사용을 줄이고 대규모 n에서 안정적입니다.
// 반복문 기반 구간 합 쿼리 (Bottom-Up)
long long queryIter(int ql, int qr) {
long long sum = 0;
for (ql += n_, qr += n_; ql <= qr; ql /= 2, qr /= 2) {
if (ql % 2 == 1) sum += tree_[ql++];
if (qr % 2 == 0) sum += tree_[qr--];
}
return sum;
}
// 주의: 이 방식은 트리 레이아웃이 다름 (2n 크기, 인덱스 n..2n-1에 리프)2. 펜윅 트리 캐시 최적화
i += (i & -i)와 i -= (i & -i)는 비트 연산이라 매우 빠릅니다. tree_를 연속 메모리에 두면 캐시 히트율이 좋습니다.
// tree_를 vector로 연속 할당 - 캐시 친화적
std::vector<long long> tree_;3. 트라이 메모리 절약 (맵 기반)
알파벳 26개가 아닌 희소한 문자 집합이면 array<26> 대신 unordered_map을 쓰면 메모리를 줄일 수 있습니다.
// 26개 자식 대신 맵 사용 (문자 집합이 작을 때)
std::unordered_map<char, std::unique_ptr<Node>> children;4. 세그먼트 트리 lazy propagation (구간 업데이트)
구간 [L,R] 전체에 delta를 더하는 업데이트가 필요하면, lazy propagation으로 O(log n)에 처리할 수 있습니다.
// Lazy 세그먼트 트리: 구간 [L,R]에 delta 더하기
// lazy[node]: 이 노드가 담당하는 구간 전체에 더해질 값
void updateRange(int node, int l, int r, int ql, int qr, long long delta) {
if (lazy[node] != 0) {
tree_[node] += lazy[node] * (r - l + 1);
if (l != r) {
lazy[2*node] += lazy[node];
lazy[2*node+1] += lazy[node];
}
lazy[node] = 0;
}
if (qr < l || r < ql) return;
if (ql <= l && r <= qr) {
tree_[node] += delta * (r - l + 1);
if (l != r) {
lazy[2*node] += delta;
lazy[2*node+1] += delta;
}
return;
}
int mid = (l + r) / 2;
updateRange(2*node, l, mid, ql, qr, delta);
updateRange(2*node+1, mid+1, r, ql, qr, delta);
tree_[node] = tree_[2*node] + tree_[2*node+1];
}5. 벤치마크 참고 (n=100,000, 쿼리 100,000회)
| 자료구조 | 쿼리 유형 | 예상 시간 |
|---|---|---|
| 단순 배열 순회 | 구간 합 | 수 초 (TLE) |
| prefix sum (업데이트 없음) | 구간 합 | ~10ms |
| 펜윅 트리 | 구간 합 + 업데이트 | ~20ms |
| 세그먼트 트리 | 구간 합 + 업데이트 | ~30ms |
| 세그먼트 트리 | 구간 최소 + 업데이트 | ~35ms |
| 트라이 | 접두사 검색 (m=10) | ~5ms (1만 단어 기준) |
8. 프로덕션 패턴
8.1 범용 세그먼트 트리 (템플릿)
template<typename T, typename Merge>
class SegmentTreeGeneric {
std::vector<T> tree_;
int n_;
Merge merge_;
T identity_;
public:
SegmentTreeGeneric(const std::vector<T>& arr, Merge merge, T identity)
: n_(static_cast<int>(arr.size())), merge_(merge), identity_(identity) {
tree_.resize(4 * n_);
build(1, 0, n_ - 1, arr);
}
void build(int node, int l, int r, const std::vector<T>& arr) {
if (l == r) { tree_[node] = arr[l]; return; }
int mid = (l + r) / 2;
build(2*node, l, mid, arr);
build(2*node+1, mid+1, r, arr);
tree_[node] = merge_(tree_[2*node], tree_[2*node+1]);
}
T query(int ql, int qr) {
return queryImpl(1, 0, n_-1, ql, qr);
}
T queryImpl(int node, int l, int r, int ql, int qr) {
if (qr < l || r < ql) return identity_;
if (ql <= l && r <= qr) return tree_[node];
int mid = (l + r) / 2;
return merge_(
queryImpl(2*node, l, mid, ql, qr),
queryImpl(2*node+1, mid+1, r, ql, qr)
);
}
void update(int idx, const T& val) {
updateImpl(1, 0, n_-1, idx, val);
}
void updateImpl(int node, int l, int r, int idx, const T& val) {
if (idx < l || r < idx) return;
if (l == r) { tree_[node] = val; return; }
int mid = (l + r) / 2;
updateImpl(2*node, l, mid, idx, val);
updateImpl(2*node+1, mid+1, r, idx, val);
tree_[node] = merge_(tree_[2*node], tree_[2*node+1]);
}
};
// 사용: 구간 최대값
auto stMax = SegmentTreeGeneric<int>(
arr,
{ return std::max(a, b); },
INT_MIN
);8.2 트라이 기반 자동완성 서비스
#include <string>
#include <vector>
#include <algorithm>
class AutocompleteService {
Trie trie_;
std::unordered_map<std::string, int> popularity_;
public:
void addWord(const std::string& word, int score = 1) {
trie_.insert(word);
popularity_[word] += score;
}
std::vector<std::string> suggest(const std::string& prefix, int limit = 10) {
auto candidates = trie_.wordsWithPrefix(prefix);
std::sort(candidates.begin(), candidates.end(),
[this](const std::string& a, const std::string& b) {
return popularity_[a] > popularity_[b];
});
if (static_cast<int>(candidates.size()) > limit) {
candidates.resize(limit);
}
return candidates;
}
};8.3 입력 검증 및 안전한 래퍼
#include <optional>
std::optional<long long> safeQuery(SegmentTree& st, int ql, int qr, int n) {
if (ql < 0 || qr >= n || ql > qr) return std::nullopt;
return st.query(ql, qr);
}8.4 실무 활용 사례
| 도메인 | 활용 |
|---|---|
| 실시간 분석 | 구간 합/최소 (주가, 로그) |
| 검색 엔진 | 트라이 기반 자동완성, 제안 |
| 게임 | 순위표 (펜윅/세그먼트로 k번째 찾기) |
| 데이터베이스 | 인덱스 구조 (B-tree는 트리 변형) |
| 코딩 테스트 | LeetCode 307, 308, 208, 211 등 |
8.5 실전 통합 예제: 주가 구간 분석기
구간 최소값(세그먼트 트리)과 구간 합(펜윅 트리)을 함께 사용하는 예시입니다.
// 주가: 구간 최저가(SegmentTreeMin) + 구간 거래량 합(FenwickTree)
class StockAnalyzer {
SegmentTreeMin minTree_;
FenwickTree volumeTree_;
public:
StockAnalyzer(const std::vector<int>& prices, const std::vector<long long>& volumes)
: minTree_(prices), volumeTree_(static_cast<int>(volumes.size())) {
volumeTree_.init(volumes);
}
int rangeMinPrice(int left, int right) { return minTree_.query(left, right); }
long long rangeTotalVolume(int left, int right) {
return volumeTree_.rangeSum(left + 1, right + 1);
}
void updatePrice(int index, int newPrice) { minTree_.update(index, newPrice); }
void addVolume(int index, long long delta) { volumeTree_.add(index + 1, delta); }
};9. 구현 체크리스트
세그먼트 트리
- 인덱스 체계 확인 (0-indexed vs 1-indexed)
- tree 크기 4*n 이상 할당
- 병합 함수 역원/항등원 확인 (합: 0, 최소: INF, XOR: 0)
- 경계 ql > qr 처리
- 오버플로우 long long 사용 여부 검토
펜윅 트리
- 1-indexed 사용 (add(0, x) 금지)
- 역원 존재하는 연산만 (합, XOR 등)
- 구간 최소/최대는 세그먼트 트리 사용
트라이
- 메모리 unique_ptr 또는 명시적 해제
- 문자 범위 (영소문자 26, 확장 시 맵)
- 접두사 검색 wordsWithPrefix 구현
프로덕션
- 입력 범위 검증
- 대규모 n에서 스택 오버플로우 방지 (반복문 구현 고려)
- 필요 시 lazy propagation (구간 업데이트)
정리
| 항목 | 설명 |
|---|---|
| 세그먼트 트리 | 구간 쿼리+업데이트 O(log n), 합/최소/최대/XOR 등 |
| 펜윅 트리 | 누적합 O(log n), 구현 간단, 역원 필요 |
| 트라이 | 접두사 검색 O(m), 자동완성, 문자열 집합 |
핵심 원칙:
- 구간 합만 필요하면 펜윅, 최소/최대 등이면 세그먼트 트리.
- 인덱스(0 vs 1)와 경계(ql>qr)를 꼼꼼히 확인.
- 트라이는 unique_ptr로 메모리 관리.
- 프로덕션에서는 입력 검증과 lazy propagation을 고려.
자주 묻는 질문 (FAQ)
Q. 이 내용을 실무에서 언제 쓰나요?
A. 구간 쿼리, 빠른 업데이트, 순위 계산, 자동완성, 검색 제안 등에 활용합니다. 실무에서는 위 본문의 예제와 선택 가이드를 참고해 적용하면 됩니다.
Q. 선행으로 읽으면 좋은 글은?
A. 각 글 하단의 이전 글 링크를 따라가면 순서대로 배울 수 있습니다. C++ 시리즈 목차에서 전체 흐름을 확인할 수 있습니다.
Q. 더 깊이 공부하려면?
A. cppreference와 LeetCode 307(Range Sum), 208(Implement Trie), 211(Design Add and Search) 등을 풀어보세요.
한 줄 요약: 세그먼트 트리·펜윅 트리·트라이를 상황에 맞게 선택하고, 흔한 실수를 피해 실무에 적용할 수 있습니다.
참고 자료
- LeetCode - Segment Tree
- LeetCode - Trie
- 《알고리즘 설계》 - Kleinberg, Tardos
- 《Introduction to Algorithms》 (CLRS) - 15장 동적 계획법, 부록 B 트리
관련 글
- C++ 그래프 알고리즘 완벽 가이드 | BFS·DFS·다익스트라·최소신장트리 [실전]
- C++ 커스텀 자료구조 완벽 가이드 | 해시테이블·트라이·LRU 캐시·Skip List [#54-2]
- C++ 알고리즘 |