Segment Tree & Fenwick Tree
배열에서 구간 합이나 구간 최솟값을 반복적으로 쿼리하면서 원소를 업데이트해야 할 때, 단순 배열은 쿼리 O(N) 또는 업데이트 O(N)의 비용이 발생합니다. Segment Tree와 Fenwick Tree는 이 둘을 모두 O(log N)으로 처리합니다. 게임에서는 리더보드 구간 집계, 타일 맵 가중치 쿼리, 동적 이벤트 스케줄링 등에 활용됩니다.
1. Segment Tree
섹션 제목: “1. Segment Tree”1.1 구조
섹션 제목: “1.1 구조”배열: [1, 3, 5, 7, 9, 11]인덱스: 0 1 2 3 4 5
트리 (1-indexed): [36] Node 1: [0,5] 합=36 / \ [9] [27] Node 2: [0,2] Node 3: [3,5] / \ / \ [4] [5] [16] [11] Node 4-7 / \ \ [1][3] [7][9] Node 8-131.2 구현
섹션 제목: “1.2 구현”#include <vector>#include <algorithm>#include <climits>
class SegmentTree{ int _n; std::vector<long long> _tree;
void Build(const std::vector<int>& arr, int node, int start, int end) { if (start == end) { _tree[node] = arr[start]; return; } int mid = (start + end) / 2; Build(arr, 2*node, start, mid); Build(arr, 2*node+1, mid+1, end); _tree[node] = _tree[2*node] + _tree[2*node+1]; }
public: SegmentTree(const std::vector<int>& arr) : _n((int)arr.size()), _tree(4 * arr.size(), 0) { Build(arr, 1, 0, _n - 1); }
// 점 업데이트: arr[idx] += delta void Update(int node, int start, int end, int idx, int delta) { if (start == end) { _tree[node] += delta; return; } int mid = (start + end) / 2; if (idx <= mid) Update(2*node, start, mid, idx, delta); else Update(2*node+1, mid+1, end, idx, delta); _tree[node] = _tree[2*node] + _tree[2*node+1]; } void Update(int idx, int delta) { Update(1, 0, _n-1, idx, delta); }
// 구간 합 쿼리: [l, r] 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(2*node, start, mid, l, r) + Query(2*node+1, mid+1, end, l, r); } long long Query(int l, int r) { return Query(1, 0, _n-1, l, r); }};
// 사용std::vector<int> arr = {1, 3, 5, 7, 9, 11};SegmentTree st(arr);
st.Query(1, 4); // 3+5+7+9 = 24st.Update(2, 2); // arr[2] += 2 → 7st.Query(1, 4); // 3+7+7+9 = 262. Lazy Propagation — 구간 업데이트
섹션 제목: “2. Lazy Propagation — 구간 업데이트”구간 전체를 업데이트할 때 O(N)이 아닌 O(log N)으로 처리합니다.
class LazySegmentTree{ int _n; std::vector<long long> _tree, _lazy;
void Push(int node) { if (_lazy[node] != 0) { _tree[2*node] += _lazy[node]; _lazy[2*node] += _lazy[node]; _tree[2*node+1] += _lazy[node]; _lazy[2*node+1] += _lazy[node]; _lazy[node] = 0; } }
public: LazySegmentTree(int n) : _n(n), _tree(4*n, 0), _lazy(4*n, 0) {}
// 구간 [l,r]에 val 더하기 void RangeUpdate(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; _lazy[node] += val; return; } Push(node); int mid = (start + end) / 2; RangeUpdate(2*node, start, mid, l, r, val); RangeUpdate(2*node+1, mid+1, end, l, r, val); _tree[node] = _tree[2*node] + _tree[2*node+1]; } void RangeUpdate(int l, int r, long long val) { RangeUpdate(1, 0, _n-1, l, r, val); }};3. Fenwick Tree (Binary Indexed Tree)
섹션 제목: “3. Fenwick Tree (Binary Indexed Tree)”구간 합과 점 업데이트만 필요하면 Segment Tree보다 구현이 단순하고 메모리가 절반입니다.
class FenwickTree{ int _n; std::vector<long long> _bit;
int LowBit(int i) { return i & (-i); }
public: FenwickTree(int n) : _n(n), _bit(n + 1, 0) {}
// 점 업데이트: arr[i] += delta (1-indexed) void Update(int i, long long delta) { for (; i <= _n; i += LowBit(i)) _bit[i] += delta; }
// 접두사 합: arr[1..i] long long PrefixSum(int i) const { long long sum = 0; for (; i > 0; i -= LowBit(i)) sum += _bit[i]; return sum; }
// 구간 합: arr[l..r] long long RangeSum(int l, int r) { return PrefixSum(r) - PrefixSum(l - 1); }};
// 사용 (1-indexed)FenwickTree ft(6);int arr[] = {1, 3, 5, 7, 9, 11};for (int i = 0; i < 6; i++) ft.Update(i+1, arr[i]);
ft.RangeSum(2, 5); // 3+5+7+9 = 24ft.Update(3, 2); // arr[3] += 2ft.RangeSum(2, 5); // 3+7+7+9 = 264. 자료구조 비교
섹션 제목: “4. 자료구조 비교”| 항목 | Segment Tree | Fenwick Tree |
|---|---|---|
| 구간 합 쿼리 | O(log N) | O(log N) |
| 점 업데이트 | O(log N) | O(log N) |
| 구간 업데이트 | O(log N) (Lazy) | O(log N) (차분 배열) |
| 구간 최솟값 | O(log N) | 불가 |
| 메모리 | O(4N) | O(N) |
| 구현 복잡도 | 중간 | 낮음 |
5. 게임 개발 활용 사례
섹션 제목: “5. 게임 개발 활용 사례”5.1 리더보드 구간 집계
섹션 제목: “5.1 리더보드 구간 집계”// 점수 업데이트가 잦고, 특정 랭크 구간 합계를 자주 조회FenwickTree leaderboard(10000); // 최대 플레이어 수
void UpdateScore(int playerId, int scoreDelta){ leaderboard.Update(playerId, scoreDelta);}
long long GetTotalScoreInRange(int rankStart, int rankEnd){ return leaderboard.RangeSum(rankStart, rankEnd);}5.2 타일 맵 가중치 쿼리
섹션 제목: “5.2 타일 맵 가중치 쿼리”// 2D Segment Tree로 직사각형 구간 합 쿼리// 적 밀도, 자원량, 영향력 맵 등에 활용class SegmentTree2D{ // 2D Fenwick Tree로 구현 (x, y 각 축에 BIT 적용) int _rows, _cols; std::vector<std::vector<long long>> _bit;
public: SegmentTree2D(int rows, int cols) : _rows(rows), _cols(cols), _bit(rows+1, std::vector<long long>(cols+1, 0)) {}
void Update(int r, int c, long long delta) { for (int i = r; i <= _rows; i += i & (-i)) for (int j = c; j <= _cols; j += j & (-j)) _bit[i][j] += delta; }
long long Query(int r, int c) const { long long sum = 0; for (int i = r; i > 0; i -= i & (-i)) for (int j = c; j > 0; j -= j & (-j)) sum += _bit[i][j]; return sum; }
long long RangeQuery(int r1, int c1, int r2, int c2) { return Query(r2,c2) - Query(r1-1,c2) - Query(r2,c1-1) + Query(r1-1,c1-1); }};- Segment Tree는 구간 합·최솟값·최댓값 쿼리와 점/구간 업데이트를 모두 O(log N)에 처리한다.
- Fenwick Tree는 구간 합과 점 업데이트만 필요할 때 Segment Tree보다 메모리가 절반이고 구현이 단순하다.
- 구간 전체 업데이트가 빈번하면 Lazy Propagation을 적용한 Segment Tree를 사용한다.
- 2D Fenwick Tree는 타일 맵 구간 집계처럼 2차원 배열의 직사각형 쿼리에 활용된다.