[C++로 배우는 알고리즘과 자료구조 심화] Day 2: 세그먼트 트리 (Segment Tree)

세그먼트 트리 (Segment Tree)

세그먼트 트리는 주어진 배열의 구간에 대한 정보를 효율적으로 저장하고 쿼리를 처리하기 위해 사용하는 트리 구조입니다. 세그먼트 트리는 다음과 같은 연산을 빠르게 수행할 수 있습니다:

1. 구간 합: 배열의 특정 범위에 대한 합을 구합니다.
2. 구간 최솟값/최댓값: 배열의 특정 범위에 대한 최솟값 또는 최댓값을 구합니다.
3. 구간 갱신: 배열의 특정 범위에 값을 갱신합니다.

세그먼트 트리의 주요 특징

1. 시간 복잡도:
   • 빌드: (O(n))
   • 쿼리: (O(\log n))
   • 업데이트: (O(\log n))
2. 구현 방법:
   • 트리의 각 노드는 배열의 특정 구간을 나타냅니다.
   • 루트 노드는 전체 배열을 나타내고, 각 자식 노드는 배열의 절반 구간을 나타냅니다.

세그먼트 트리의 기본 연산

1. 트리 빌드: 초기 배열을 기반으로 세그먼트 트리를 빌드합니다.
2. 쿼리: 특정 구간에 대한 정보를 쿼리합니다.
3. 업데이트: 특정 구간의 값을 업데이트합니다.

세그먼트 트리의 구현

다음은 C++로 세그먼트 트리를 구현한 예제입니다. 구간 합을 구하고 구간 값을 업데이트하는 연산을 포함합니다.

 

세그먼트 트리 노드 정의 및 클래스 선언

#include <iostream>
#include <vector>
#include <cmath>

// 세그먼트 트리 클래스 정의
class SegmentTree {
public:
    SegmentTree(const std::vector<int>& data);
    int query(int left, int right); // 구간 합 쿼리 함수
    void update(int index, int value); // 구간 값 업데이트 함수

private:
    std::vector<int> tree; // 세그먼트 트리 배열
    int n; // 원본 배열의 크기

    void build(const std::vector<int>& data, int node, int start, int end); // 트리 빌드 함수
    int query(int node, int start, int end, int left, int right); // 쿼리 함수
    void update(int node, int start, int end, int index, int value); // 업데이트 함수
};

 

트리 빌드 함수 정의

// 세그먼트 트리 생성자 정의
SegmentTree::SegmentTree(const std::vector<int>& data) {
    n = data.size();
    int height = std::ceil(std::log2(n));
    int maxSize = 2 * std::pow(2, height) - 1;
    tree.resize(maxSize, 0);
    build(data, 0, 0, n - 1);
}

// 트리 빌드 함수 정의
void SegmentTree::build(const std::vector<int>& data, int node, int start, int end) {
    if (start == end) {
        tree[node] = data[start];
    } else {
        int mid = (start + end) / 2;
        build(data, 2 * node + 1, start, mid);
        build(data, 2 * node + 2, mid + 1, end);
        tree[node] = tree[2 * node + 1] + tree[2 * node + 2];
    }
}

 

쿼리 함수 정의

// 구간 합 쿼리 함수 정의
int SegmentTree::query(int left, int right) {
    return query(0, 0, n - 1, left, right);
}

// 구간 합 쿼리 함수 정의 (재귀적 구현)
int SegmentTree::query(int node, int start, int end, int left, int right) {
    if (right < start || end < left) {
        return 0; // 범위 밖인 경우
    }
    if (left <= start && end <= right) {
        return tree[node]; // 범위 안인 경우
    }
    int mid = (start + end) / 2;
    int sumLeft = query(2 * node + 1, start, mid, left, right);
    int sumRight = query(2 * node + 2, mid + 1, end, left, right);
    return sumLeft + sumRight;
}

 

업데이트 함수 정의

// 구간 값 업데이트 함수 정의
void SegmentTree::update(int index, int value) {
    update(0, 0, n - 1, index, value);
}

// 구간 값 업데이트 함수 정의 (재귀적 구현)
void SegmentTree::update(int node, int start, int end, int index, int value) {
    if (start == end) {
        tree[node] = value;
    } else {
        int mid = (start + end) / 2;
        if (index <= mid) {
            update(2 * node + 1, start, mid, index, value);
        } else {
            update(2 * node + 2, mid + 1, end, index, value);
        }
        tree[node] = tree[2 * node + 1] + tree[2 * node + 2];
    }
}

 

사용 예제

int main() {
    std::vector<int> data = {1, 3, 5, 7, 9, 11};
    SegmentTree segTree(data);

    std::cout << "구간 합 (1, 3): " << segTree.query(1, 3) << std::endl; // 3 + 5 + 7 = 15
    segTree.update(1, 10);
    std::cout << "구간 합 (1, 3) 업데이트 후: " << segTree.query(1, 3) << std::endl; // 10 + 5 + 7 = 22

    return 0;
}

 

설명

1. 트리 빌드:
   • build: 주어진 배열을 기반으로 세그먼트 트리를 빌드합니다. 각 노드는 해당 구간의 합을 저장합니다.
2. 구간 합 쿼리:
   • query: 특정 구간의 합을 쿼리합니다. 재귀적으로 트리의 노드를 탐색하여 구간 합을 계산합니다.
3. 구간 값 업데이트:
   • update: 특정 인덱스의 값을 업데이트합니다. 재귀적으로 트리의 노드를 탐색하여 값을 갱신합니다.

세그먼트 트리의 기본 개념과 구현 방법을 이해했습니다.

질문이나 피드백이 있으면 언제든지 댓글로 남겨 주세요. 내일은 "Day 3: 펜윅 트리(Fenwick Tree, Binary Indexed Tree)"에 대해 학습하겠습니다.