세그먼트 트리(Segment Tree) - 이진 트리(Binary Tree)의 응용

 세그먼트 트리(Segment Tree)는 제목에 적힌 것처럼 이진 트리에서 응용된 트리이다. 세그먼트 트리는 여러 개의 데이터가 순서를 가지고 존재할 때, 특정 범위의 합을 구할 때 사용된다. 물론 데이터의 변경이 없다면 특정 범위의 합을 구하는 문제에서 동적 프로그래밍(DP)를 사용해도 괜찮다.

 만약 주어진 데이터의 숫자가 지속적으로 변경되고 여러 번 특정 구간에 대해 합을 구해야 한다면 동적 프로그래밍(DP)의 사용이 적절할까?? 아니다. 데이터가 여러 번 바뀌고 구간 합을 여러 번 구해야 하는 상황이라면 동적 프로그래밍(DP)는 데이터가 바뀔 때마다 O(N) 시간복잡도를 가질 것이고, 데이터가 변경되는 횟수가 M이라면 총 O(NM)의 시간복잡도를 가진다.

 

  그렇다면 세그먼트 트리의 경우는 어떨까? 세그먼트 트리의 경우 데이터를 변경하거나 구간의 대표 값(합, 최대, 최소, GCD 등)을 구하는 데에 걸리는 시간복잡도는 O(logN)이 된다. 이유는 트리의 구조에 있다. 

세그먼트 트리 예시 (Leaf node 의 개수가 7개이고 최소 값을 구하는 트리)

 세그먼트 트리는 총 데이터 개수가 N개 라면, 리프 노드의 개수가 N개 이상이 되는 이진 트리로 구성된다. 아래 그림처럼 7개라면, 리프노드의 개수가 7개 이상이 되는 이진 트리를 초기에 구성되고 해당 트리의 높이는 log2(2N - 1)이 되므로 해당 트리안의 노드 값이 업데이트 되거나 구간의 대표 값(합, 최대, 최소, GCD 등) 걸리는 시간복잡도는 O(logN)이 될 수 있는 것이다.

 

 세그먼트 트리는 인덱스 트리(Index Tree)와는 달리 구간의 대표 값(합, 최대, 최소, GCD 등)을 Top down 방식으로 구한다. (인덱스 트리는 Bottom up 방식으로 값을 구한다)

 세그먼트 트리의 구성 방식은 https://visualgo.net/en/segmenttree 이 링크를 타고 들어가서 직접 시각적으로 보면서 만들어보면 알 수 있을 것이다.

 

 세그먼트 트리 구성에 쓰이는 코드와 세그먼트 트리에서 구간 합을 구하는 코드를 첨부합니다. (백준 - 1655번)

#include <bits/stdc++.h>

using namespace std;

int N, M, K;
long long arr[1000005];

long long makeSegmentTree(vector<long long>& segmentTree, int node, int start, int end) {
    if (start == end) {
        return segmentTree[node] = arr[start];
    }
    int mid = (start + end) / 2;

    return segmentTree[node] = makeSegmentTree(segmentTree, node * 2, start, mid) + makeSegmentTree(segmentTree, node * 2 + 1, mid + 1, end);
}

void updateSegmentTree(vector<long long>& segmentTree, int node, int start, int end, int idx, long long diff) {
    if (idx < start || idx > end) return;
    segmentTree[node] += diff;
    if (start != end) {
        int mid = (start + end) / 2;
        updateSegmentTree(segmentTree, node * 2, start, mid, idx, diff);
        updateSegmentTree(segmentTree, node * 2 + 1, mid + 1, end, idx, diff);
    }
}

long long sumSegmentTree(vector<long long>& segmentTree, int node, int left, int right, int start, int end) {
    //범위 밖의 경우
    if (left > end || right < start) return 0;
    //범위 안의 경우
    if (left <= start && right >= end) return segmentTree[node];

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

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> M >> K;
   
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }
    int treeDepth = ceil(log2(N));  //log2 취해준 뒤, 올림 함수
    int treeSize = 1 << (treeDepth + 1);        //2^(treeDepth + 1)
    //트리에서 0번 인덱스는 사용하지 않으므로 treeSize만큼 vector 할당받아서 사용한다. (원래 트리 사이즈는 treeSize - 1이다)
    vector<long long> segmentTree(treeSize);

    makeSegmentTree(segmentTree, 1, 0, N - 1);

    for (int i = 0; i < M + K; i++) {
        int a, b;
        long long c;

        cin >> a >> b >> c;
        if (a == 1) {       //number update
            updateSegmentTree(segmentTree, 1, 0, N - 1, b - 1, c - arr[b - 1]);
            arr[b - 1] = c;
        }
        else {          //print sum
            cout << sumSegmentTree(segmentTree, 1, b - 1, c - 1, 0, N - 1) << '\n';
        }
    }
}

 

출처 

• https://visualgo.net/en/segmenttree