구간 합 알고리즘 - 세그먼트 트리

알고리즘 문제에서 종종 배열이나 리스트 내 특정 구간의 원소들의 합을 계산해야 할 때가 있을 것이다 이럴 때 쓰이는 알고리즘을 구간 합이라고 한다 이러한 구간 합 알고리즘에는 크게 누적 합 배열(prefix sum array)과 세그먼트 트리(segment tree)가 존재하는데

이번 글에선 배열의 값이 변경되는 경우에도 사용할 수 있는 세그먼트 트리 알고리즘에 대해 소개하려고 한다

세그먼트 트리(Segment Tree)란?

세그먼트 트리는 정확히는 알고리즘이 아닌 자료구조로 이진 트리를 기반으로 하여 셋그먼트 트리에 각 노드는 배열의 특정 부분 구간을 나타내며 이 구간의 집계 정보(예: 합, 최대값, 최소값)를 저장 가진다

이로 인해 세그먼트 트리는 배열의 특정 구간에 대한 연산(합, 최소/최대값 등)을 효율적으로 처리할 수 있다

이렇게만 설명하면 잘 이해가 안될 수 있으니 도서관의 책 분류 시스템 비유해서 설명하면

큰 도서관에 수많은 책이 있고 이 책들을 어떤 기준으로 분류해야 한다고 할 때 여기서 도서관의 책들이 배열의 원소들이고 각 책의 특정 정보 예를 들어 페이지 수가 원소의 값이라고 할 때

모든 책을 일일이 살펴보며 분류하는 것은 시간이 많이 걸릴 것이다 여기서 세그먼트 트리는 이 문제를 해결하기 위해 도서관을 여러 섹션으로 나누는데 각 섹션은 특정 범위의 책들을 포함하며 그 섹션의 책들에 대한 정보(총 페이지 수)를 요약해 둔다

그 후 만약 새 책이 추가되거나 기존의 책 정보가 바뀔 때는 굳이 전체 도서관의 모든 책을 다시 분류할 필요 없이 해당되는 섹션만 업데이트하면 훨씬 효율적으로 처리할 수 있다

그리고 이 방법을 쓰면 특정 범위의 책에 대한 정보를 찾아보는 것 또한 일일히 모든 책을 보는 것이 아닌 미리 정리해둔 섹션별 정보를 활용하여 빠르게 답을 찾을 수 있는데

이것이 세그먼트 트리가 업데이트를 처리하는 방식이다

세그먼트 트리의 주요 기능

이러한 세그먼트 트리의 주요 기능을 요약하면

• 초기화: 배열에 대한 세그먼트 트리를 구성한다
• 질의(Query): 주어진 범위에 대한 결과(합, 최소/최대값 등)를 반환한다
• 갱신(Update): 배열의 특정 원소가 변경될 때 트리를 업데이트한다

이렇게 크게 3개로 요약할 수 있다

세그먼트 트리의 장단점

그렇다면 세그먼트는 어떤한 장담점을 가지고 있을까? 세그먼트 트리의 장점으로는 여러 번의 구간 질의를 빠르게 처리할 수 있다는 점과 배열의 일부가 변경되어도 효율적으로 업데이트 가능하다는 점이 있지만

다른 기본적인 자료구조들이나 같은 구간 합 알고리즘에서 사용하는 누적 합 배열에 비해 복잡하다 그렇기에 꼭 누적 합 배열로 처리할 수 없는 데이터가 변경되는 경우에만 사용하는 것이 좋다

세그먼트 트리 구현 (C++)

세그먼트 트리를 C++로 구현하는 법을 살펴보며 글을 마치겠다 아래는 구간 합을 계산하는 세그먼트 트리의 간단한 C++ 구현 예제이다

#include <iostream>
#include <vector>

using namespace std;

class SegmentTree {
private:
    vector<int> tree;
    vector<int> arr;  // 원본 배열
    int n;

    int init(int node, int start, int end) {
        if (start == end) {
            return tree[node] = arr[start];
        }
        int mid = (start + end) / 2;
        return tree[node] = init(node*2, start, mid) + init(node*2+1, mid+1, end);
    }

    int query(int node, int start, int end, int left, int right) {
        if (left > end || right < start) return 0;
        if (left <= start && end <= right) return tree[node];
        int mid = (start + end) / 2;
        return query(node*2, start, mid, left, right) + query(node*2+1, mid+1, end, left, right);
    }

public:
    SegmentTree(const vector<int>& array) {
        arr = array;
        n = array.size();
        tree.resize(4*n);
        init(1, 0, n-1);
    }

    int getSum(int left, int right) {
        return query(1, 0, n-1, left, right);
    }
};

int main() {
    vector<int> nums = {3, 2, -1, 6, 5};
    SegmentTree st(nums);

    // 구간 합 예시: nums[1, 3]
    cout << "nums[1, 3]: " << st.getSum(1, 3) << endl;

    return 0;
}