[c++] 세그먼트 트리를 이용한 검색

15 Dec 2023

세그먼트 트리(segment tree)는 효율적인 범위 조회를 위해 사용되는 자료 구조입니다. 이 구조를 사용하면 배열과 같은 시퀀스 데이터를 효과적으로 다룰 수 있습니다. 이는 대규모 데이터에서 주어진 범위 내의 값에 대한 조회 및 연산을 빠르게 수행할 수 있게 해줍니다.

세그먼트 트리란?

세그먼트 트리는 주어진 배열 혹은 리스트를 사용하여 구성되며, 각 노드는 해당 구간의 값을 나타냅니다. 이 구간을 효과적으로 나누어 관리함으로써, 주어진 범위에 대한 조회 연산을 $O(\log n)$의 시간 복잡도로 수행할 수 있습니다.

세그먼트 트리의 사용

아래 예제는 C++을 사용하여 세그먼트 트리를 구현하여 범위 내의 최솟값을 조회하는 간단한 코드입니다.

#include <vector>
#include <climits>

using namespace std;

class SegmentTree {
private:
    vector<int> tree;
    int n;

    int build(vector<int>& arr, int node, int start, int end) {
        if (start == end) {
            tree[node] = arr[start];
            return tree[node];
        } else {
            int mid = (start + end) / 2;
            tree[node] = min(build(arr, 2 * node + 1, start, mid), build(arr, 2 * node + 2, mid + 1, end));
            return tree[node];
        }
    }

    int query(int node, int start, int end, int left, int right) {
        if (right < start || end < left) return INT_MAX;
        if (left <= start && end <= right) return tree[node];

        int mid = (start + end) / 2;
        return min(query(2 * node + 1, start, mid, left, right), query(2 * node + 2, mid + 1, end, left, right));
    }

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

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

이 구현은 주어진 배열을 바탕으로 세그먼트 트리를 구축하고, 트리에서 최솟값을 조회하기 위한 query 함수를 제공합니다.

이제, 세그먼트 트리를 사용하여 배열의 범위 내에서의 조회를 간단하게 수행할 수 있습니다.

결론

세그먼트 트리는 주어진 범위에 대한 조회 및 연산을 빠르게 수행하기 위한 효과적인 자료 구조로, 대규모 데이터 처리 및 검색 문제를 효과적으로 해결할 수 있습니다. C++을 사용한 위의 예시 코드를 통해 세그먼트 트리를 더 잘 이해할 수 있을 것입니다.

더 많은 자료 구조 및 알고리즘에 대한 내용은 이 링크를 참고해주세요.