[자료구조 및 알고리즘] 세그먼트 트리

세그먼트 트리

세그먼트 트리는 효율적인 구간 연산을 처리하기 위해 사용되는 트리 구조이다. 주어진 배열에서 특정 구간의 합이나 최대값/최소값 등과 같은 정보를 빠르게 구해야 할 때 유용하다. 이 구조를 사용하면 배열의 값을 업데이트하거나 구간의 값을 구하는 작업을 빠르게 처리할 수 있다.

 

1. 세그먼트 트리란 무엇인가

세그먼트 트리는 주어진 배열을 관리하는 트리 구조로, 배열의 특정 구간에 대한 연산(예: 합, 최대값, 최소값 등)을 효율적으로 처리하는 데 사용된다. 일반적으로 배열의 크기가 커질수록 배열의 구간 합이나 구간 최대/최소를 구하는 시간이 오래 걸리는데, 세그먼트 트리를 사용하면 로그 시간(O(logN)))에 이런 연산을 처리할 수 있다. 즉, 세그먼트 트리는 배열의 구간 정보를 미리 저장해 두어, 나중에 필요할 때 빠르게 사용할 수 있도록 하는 구조이다.

 

2. 세그먼트 트리의 작동 원리

세그먼트 트리는 이진 트리 형태로, 배열을 작은 구간으로 나누어 각 구간의 정보를 저장하는 방식으로 작동한다.

• 리프 노드(트리의 가장 아래쪽 노드)들은 배열의 개별 요소를 나타낸다.
• 부모 노드는 그 자식 노드들이 나타내는 구간의 정보를 저장한다. 예를 들어, 자식 노드들이 나타내는 구간의 합이나 최대값을 부모 노드에 저장한다.

세그먼트 트리는 트리구조이기 때문에 깊이는 약 log2(N)이며, 각 노드에서 저장하는 정보는 구간을 나타낸다. 이렇게 구간 정보를 트리에 저장해두면, 구간 연산을 빠르게 처리할 수 있다.

 

예시

배열 [1, 3, 5, 7, 9, 11] 이 있다고 가정하고, 이 배열을 세그먼트 트리로 만들면 다음과 같은 구조가 된다.

• 리프 노드들은 배열의 각 요소를 저장한다.
• 그 위의 부모 노드들은 자식 노드들이 나타내는 구 개의 값의 합을 저장한다.

세그먼트 트리

• 위의 트리에서 구간 [1, 6]의 합을 구하고 싶으면 루트 노드에서 바로 답을 얻을 수 있다.
• 만약 구간 [3, 5]의 합을 구하려면, 트리의 특정 부분으로 내려가서 구간을 합산한다.

이처럼 세그먼트 트리는 각 구간의 연산을 미리 계산해 트리에 저장하고, 이후 구간에 대한 쿼리가 들어오면 미리 계산된 값을 사용해 빠르게 답을 얻는다.

 

3. 세그먼트 트리를 사용하는 이유

세그먼트 트리가 필요한 이유는 효율성 때문이다. 만약 일반 배열에서 특정 구간의 합을 구하려면 매번 그 구간을 전부 순회하면서 계산해야 한다. 배열이 클수록 시간이 많이 걸린다. 세그먼트 트리를 사용하면 다음과 같은 이점이 있다.

1. 빠른 구간 쿼리
   • 세그먼트 트리는 구간 연산(구간 합, 구간 최대값/최소값)을 O(logN)에 처리할 수 있다.
   • 일반적으로 배열에서 구간 연산을 처리하는 데는 O(N)의 시간이 걸리지만 세그먼트 트리를 사용하면 훨씬 더 빠르게 구간 정보를 얻을 수 있다.
2. 빠른 업데이트
   • 배열에서 특정 값을 업데이트해야 하는 상황이 있을 수 있다. 예를 들어 배열의 특정 값이 변경될 때마다 그 값을 반영해서 구간 합을 업데이트해야 한다면, 세그먼트 트리를 사용하면 O(logN)에 값을 갱신할 수 있다.
   • 일반 배열에서는 값이 변경될 때 구간 합을 다시 계산해야 하므로, 업데이트와 구간 합을 모두 효율적으로 처리하기 어렵다.
3. 다양한 연산 지원
   • 세그먼트 트리는 합뿐만 아니라 최대값, 최소값, 곱, XOR 등 다양한 구간 연산을 처리할 수 있다.
   • 이러한 다양한 연산을 지원하기 때문에, 세그먼트 트리는 많은 문제에서 유용하게 사용된다.

4. 세그먼트 트리의 사용 예시

세그먼트 트리는 PS 뿐만 아니라 다양한 상황에서 사용될 수 있다.

• 주식시장: 주가의 특정 구간에서 최대값, 최소값, 구간 합을 빠르게 계산할 수 있다.
• 스포츠 분석: 특정 구간 동안의 팀 점수나 성적을 빠르게 계산할 때 유용하다.
• 게임 개발: 맵의 특정 구간에서 자원 상태나 적의 수를 빠르게 확인하고 업데이트 하는 데 사용될 수 있다.
• 금융 데이터 분석: 주어진 구간 동안의 평균, 최대값, 최소값 등을 계산할 때 매우 효율적이다.

5. 코드

아래는 https://www.acmicpc.net/problem/2042 구간 합 구하기의 정답 코드이다.

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

using namespace std;
typedef long long ll;

ll n,k,m,a,b,c,num[1000004];

// 세그먼트 트리를 처음 만드는 함수
void init(vector<ll> &tree, int node, int start, int end) {
    if(start == end) {
    	// 리프노드의 경우에는 해당 배열 값 할당
        tree[node] = num[start];
    } else {
    	// 반으로 나눠서 왼쪽 노드, 오른쪽 노드 탐색 및 노드 채우기
        int mid = (start + end) / 2;
        init(tree, node*2, start, mid);
        init(tree, node*2 + 1, mid + 1, end);
        tree[node] = tree[node*2] + tree[node*2 + 1];
    }
}

// 구간 쿼리를 구하는 함수
ll query(vector<ll> &tree, int node, int start, int end, int left, int right) {
	// 범위를 벗어난 경우에는 0을 반환 
    if(left > end || right < start) return 0;
    // 탐색하는 노드가 합을 구해야 하는 범위에 속한 경우 그 노드에 저장된 값을 반환
    if(left <= start && right >= end) {
        return tree[node];
    }
    // 두 케이스를 제외하면, 왼쪽 자식과 오른쪽 자식을 루트로 하는 트리에서 다시 탐색
    int mid = (start + end) / 2;
    ll lsum = query(tree, node*2, start, mid, left, right);
    ll rsum = query(tree, node*2 + 1, mid + 1, end, left, right);
    return lsum + rsum;
}

// 값을 업데이트 하는 함수
void update(vector<ll> &tree, int node, int start, int end, int idx, ll val) {
	// 인덱스가 범위를 벗어나면 함수 종료
    if(idx > end || idx < start) return;
    // 리프 노드인 경우, 배열의 값과 트리 노드 값 변경
    if(start == end) {
        num[idx] = val;
        tree[node] = val;
        return;
    }
    // 변경 후 왼쪽 노드와 오른쪽 노드를 탐색하여 값을 변경
    update(tree, node*2, start, (start+end)/2, idx, val);
    update(tree, node*2 + 1, (start + end) / 2 + 1, end, idx, val);
    // 부모 노드는 왼쪽 자식 노드와 오른쪽 자식 노드의 합(구간 합이므로)
    tree[node] = tree[node*2] + tree[node*2 + 1];
}

int main() {
    cin >> n >> k >> m;
    for(int i = 0; i < n; i++) cin >> num[i];
    // 트리의 높이는 아래 식으로 구할 수 있음
    int h = (int)ceil(log2(n));
    // 트리의 사이즈는 2^(h+1)로 구하거나
    // 단순히 4*n으로 정할 수 있다.
    int tree_size = (1 << (h+1));
    vector<ll> tree(tree_size);
    init(tree, 1, 0, n - 1);
    for(int i = 0; i < k + m; i++) {
        cin >> a >> b >> c;
        if(a == 1) {
            update(tree, 1, 0, n - 1, b - 1,c);
        } else if (a == 2) {
            ll res = query(tree, 1, 0,n - 1 ,b - 1, c - 1);
            cout << res << '\n';
        }
    }
    return 0;
}

6. 마무리

세그먼트 트리는 배열의 특정 구간에 대한 정보를 빠르게 처리하기 위해 만들어진 자료 구조이다. 구간 연산과 값의 업데이트를 모두 효율적으로 처리할 수 있어, 특히 대규모 데이터에서 매우 유용하게 사용된다고 한다.