세그먼트 트리(Segment Tree)는 트리 자료구조를 기반으로 하는 범위 질의(Range Query) 문제를 해결하기 위한 효율적인 방법입니다. 이 자료구조는 수열의 구간 합이나 최소값 등을 빠르게 처리할 수 있는 장점이 있습니다. C언어로 구현하는 방법에 대해 알아보겠습니다.

세그먼트 트리의 개념

세그먼트 트리는 주어진 배열을 이진트리 형태로 표현합니다. 각 노드는 해당 구간의 합 또는 최소값 등을 저장하며, 리프 노드는 주어진 배열의 각 요소를 나타냅니다. 세그먼트 트리의 중간 노드는 해당 구간의 합 등을 계산하여 저장하고, 이를 통해 빠르게 범위 질의를 수행할 수 있습니다.

세그먼트 트리의 구현

아래는 C언어를 사용하여 세그먼트 트리를 구현하는 간단한 예제 코드입니다. 여기서는 구간의 합을 구하는 기능을 포함하고 있습니다.

#include <stdio.h>

#define N 100000
int tree[4*N];

int build_tree(int a[], int v, int tl, int tr) {
    if (tl == tr) {
        tree[v] = a[tl];
    } else {
        int tm = (tl + tr) / 2;
        build_tree(a, v*2, tl, tm);
        build_tree(a, v*2+1, tm+1, tr);
        tree[v] = tree[v*2] + tree[v*2+1];
    }
}

int query(int v, int tl, int tr, int l, int r) {
    if (l > r) 
        return 0;
    if (l == tl && r == tr) {
        return tree[v];
    }
    int tm = (tl + tr) / 2;
    return query(v*2, tl, tm, l, min(r, tm))
           + query(v*2+1, tm+1, tr, max(l, tm+1), r);
}

위의 코드는 세그먼트 트리를 구축하고 구간의 합을 쿼리하는 기능을 제공합니다. build_tree() 함수는 주어진 배열을 이용하여 세그먼트 트리를 구축하고, query() 함수는 주어진 구간의 합을 계산합니다.

마치며

세그먼트 트리는 범위 질의 문제를 해결하는데 있어서 매우 유용한 자료구조입니다. C언어를 사용하여 구현하는 방법을 이해하는 것은 이러한 문제를 해결하는 데 도움이 될 것입니다.

더 자세한 내용은 GeeksforGeeks와 CP-Algorithms를 참고하시기 바랍니다.