세그먼트 트리(Segment Tree) 비재귀 구현 (메모리와 속도 최적화 팁)

알고리즘 문제를 풀다 보면 구간 쿼리(Range Query)를 효율적으로 처리해야 하는 상황이 자주 발생합니다. 특히 코딩 테스트나 competitive programming에서 세그먼트 트리(Segment Tree)는 필수적인 자료구조로 자리 잡았습니다. 하지만 재귀 방식의 세그먼트 트리는 함수 호출 오버헤드와 스택 메모리 사용으로 인해 성능 저하가 발생할 수 있습니다. 이 글에서는 비재귀(Iterative) 방식으로 세그먼트 트리를 구현하여 메모리와 속도를 동시에 최적화하는 방법을 상세히 다룹니다.

1. 세그먼트 트리의 기본 개념과 필요성

세그먼트 트리는 배열의 구간에 대한 질의를 O(log N) 시간에 처리할 수 있는 트리 기반 자료구조입니다. 구간 합(Range Sum), 구간 최솟값(Range Minimum), 구간 최댓값(Range Maximum) 등 다양한 연산을 빠르게 수행할 수 있습니다.

1-1. 세그먼트 트리가 필요한 상황

구간 합 쿼리: 배열의 특정 구간 [L, R]의 합을 빠르게 계산해야 할 때
구간 최솟값/최댓값: 주어진 구간에서 최솟값이나 최댓값을 찾아야 할 때
업데이트와 쿼리 혼재: 배열의 값이 동적으로 변경되면서 동시에 구간 쿼리를 수행해야 할 때
시간 복잡도 요구사항: 단순 반복문으로는 시간 초과가 발생하는 경우

1-2. 재귀 방식의 한계

전통적인 세그먼트 트리는 재귀 함수로 구현됩니다. 하지만 재귀 방식은 다음과 같은 문제점이 있습니다.

함수 호출 오버헤드: 매 쿼리마다 여러 번의 함수 호출이 발생하여 실행 시간이 증가합니다
스택 메모리 사용: 재귀 깊이가 깊어질수록 스택 오버플로우 위험이 있습니다
캐시 효율성: 재귀 호출 패턴은 CPU 캐시 지역성이 떨어집니다

2. 비재귀 세그먼트 트리의 핵심 원리

비재귀 세그먼트 트리는 배열의 인덱스를 활용하여 부모-자식 관계를 명시적으로 계산합니다. 이를 통해 재귀 없이도 트리를 순회할 수 있습니다.

2-1. 배열 기반 완전 이진 트리 구조

비재귀 세그먼트 트리는 1-indexed 배열로 구현되며, 다음과 같은 인덱스 관계를 가집니다.

노드 i의 왼쪽 자식: 2 * i
노드 i의 오른쪽 자식: 2 * i + 1
노드 i의 부모: i / 2

2-2. 메모리 최적화 기법

일반적으로 세그먼트 트리는 4N 크기의 배열이 필요하지만, 비재귀 방식에서는 2N 크기만으로 충분합니다. 이는 완전 이진 트리의 성질을 이용하여 빈 공간 없이 촘촘하게 노드를 배치하기 때문입니다.

// 기존 재귀 방식: 4N 메모리
int tree[4 * MAX_N];

// 비재귀 방식: 2N 메모리
int tree[2 * MAX_N];

3. 비재귀 세그먼트 트리 구현 코드

다음은 구간 합을 처리하는 비재귀 세그먼트 트리의 완전한 구현 예시입니다.

#include <iostream>
#include <vector>
using namespace std;

class SegmentTree {
private:
    int n; // 원본 배열 크기
    vector<long long> tree; // 세그먼트 트리 배열

public:
    // 생성자: O(N) 시간에 트리 구축
    SegmentTree(const vector<int>& arr) {
        n = arr.size();
        tree.resize(2 * n);
        
        // 리프 노드에 원본 값 저장
        for (int i = 0; i < n; i++) {
            tree[n + i] = arr[i];
        }
        
        // 상위 노드 계산 (bottom-up)
        for (int i = n - 1; i > 0; i--) {
            tree[i] = tree[2 * i] + tree[2 * i + 1];
        }
    }
    
    // 단일 값 업데이트: O(log N)
    void update(int pos, int value) {
        pos += n; // 리프 노드 인덱스로 변환
        tree[pos] = value;
        
        // 부모 노드들 업데이트
        while (pos > 1) {
            pos /= 2;
            tree[pos] = tree[2 * pos] + tree[2 * pos + 1];
        }
    }
    
    // 구간 합 쿼리: O(log N)
    long long query(int left, int right) {
        left += n;  // 리프 노드 인덱스로 변환
        right += n;
        long long sum = 0;
        
        while (left <= right) {
            // left가 오른쪽 자식이면 해당 노드 포함
            if (left % 2 == 1) {
                sum += tree[left];
                left++;
            }
            // right가 왼쪽 자식이면 해당 노드 포함
            if (right % 2 == 0) {
                sum += tree[right];
                right--;
            }
            left /= 2;
            right /= 2;
        }
        
        return sum;
    }
};

int main() {
    vector<int> arr = {1, 3, 5, 7, 9, 11};
    SegmentTree st(arr);
    
    cout << "구간 [1, 4]의 합: " << st.query(1, 4) << endl;
    
    st.update(2, 10); // 인덱스 2를 10으로 변경
    cout << "업데이트 후 구간 [1, 4]의 합: " << st.query(1, 4) << endl;
    
    return 0;
}

3-1. 코드 동작 원리 상세 분석

초기화 과정: 먼저 리프 노드(인덱스 n부터 2n-1까지)에 원본 배열 값을 저장합니다. 그 다음 인덱스 n-1부터 1까지 역순으로 순회하며 각 부모 노드를 두 자식의 합으로 채웁니다.

업데이트 과정: 변경할 위치를 리프 노드 인덱스로 변환(pos += n)한 후, 값을 갱신하고 부모 방향으로 올라가며 모든 조상 노드를 재계산합니다.

쿼리 과정: 구간의 양 끝을 리프 노드 인덱스로 변환한 후, left가 오른쪽 자식이거나 right가 왼쪽 자식일 때 해당 노드를 결과에 포함시킵니다. 이후 부모 레벨로 이동하며 구간을 좁혀갑니다.

4. 성능 최적화 추가 팁

4-1. 구간 최솟값/최댓값 구현

구간 합 대신 최솟값이나 최댓값을 구하려면 덧셈 연산을 min/max 함수로 교체하면 됩니다.

// 구간 최솟값 버전
tree[i] = min(tree[2 * i], tree[2 * i + 1]);

// 쿼리에서도 동일하게 적용
int minVal = INT_MAX;
if (left % 2 == 1) minVal = min(minVal, tree[left++]);
if (right % 2 == 0) minVal = min(minVal, tree[right--]);

4-2. 0-indexed 배열 처리

대부분의 프로그래밍 언어는 0-indexed를 사용하므로, 쿼리와 업데이트 시 인덱스 변환에 주의해야 합니다. 위 코드에서는 pos += n 연산으로 자동 변환됩니다.

4-3. 캐시 지역성 향상

배열 순차 접근: 비재귀 방식은 배열을 순차적으로 접근하므로 CPU 캐시 히트율이 높습니다
메모리 정렬: tree 배열을 16바이트 경계에 정렬하면 SIMD 최적화가 가능합니다
루프 언롤링: 컴파일러 최적화 옵션(-O2, -O3)을 활용하면 추가 성능 향상이 가능합니다

5. 실전 적용 시 주의사항

5-1. 인덱스 범위 검증

쿼리 범위가 배열 경계를 벗어나지 않도록 반드시 검증 로직을 추가해야 합니다. 특히 right < left인 경우를 처리해야 합니다.

5-2. 오버플로우 방지

구간 합 계산 시 int 범위를 초과할 수 있으므로 long long 타입을 사용하는 것이 안전합니다.

5-3. 초기값 설정

구간 최솟값을 구할 때는 INT_MAX, 최댓값을 구할 때는 INT_MIN으로 초기화해야 올바른 결과를 얻을 수 있습니다.

[핵심 요약]
1. 비재귀 세그먼트 트리는 2N 메모리만 사용하며 재귀 방식보다 2배 이상 빠릅니다.
2. 인덱스 관계(부모: i/2, 자식: 2i, 2i+1)를 활용하여 반복문으로 구현합니다.
3. 구간 합, 최솟값, 최댓값 등 다양한 연산에 적용 가능하며 캐시 효율성이 우수합니다.

이 방식은 대규모 데이터 처리나 시간 제약이 엄격한 코딩 테스트에서 특히 유용합니다. 재귀의 직관성을 포기하는 대신 실행 속도와 메모리 효율이라는 실질적인 이득을 얻을 수 있습니다.

tech-korea