[자료 구조] 세그먼트 트리

필수 선행 개념: 분할 정복, 이분 탐색

 

 

배열 arr = {1, 3, 5, 10, 2}이 있다고 해보자.

특정 구간의 최댓값, 최솟값, 구간합, 구간곱을 구한다고 할 때 질문이 하나라면 O(N)에 해결할 수 있다.

만약 질문이 10만개라면 어떨까? O(N²) = 약 11자리 이므로 1초안에 해결이 불가능하다.

이때 세그먼트 트리를 이용하면 O(log N)에 해결이 가능하다.

 

배열의 크기는 자료의 개수(N)에 대해 N보다 크거나 같은 2의 제곱수에 두배한 크기만큼 미리 할당해두어야 한다.

 

시뮬레이션

 

1. 세그먼트 트리 초기화하기

int init(int st, int en, int node){
    if(st == en) return tree[node] = arr[st];

    int mid = (st + en) / 2;
    return tree[node] = init(st, mid, node*2) + init(mid+1, en, node*2+1);
}

2. 구간 합 구하기

int sum(int st, int en, int left, int right, int node){
    //범위 밖에 있는 경우
    if(st > right || en < left) return 0;
    //범위 안에 있는 경우
    if(st >= left && en <= right) return tree[node];
    //범위가 걸쳐있는 경우
    int mid = (st + en) / 2;
    return sum(st, mid, left, right, ndoe*2) + sum(mid + 1, en, left, right, node*2+1);
}

3. tree 업데이트하기

void update(int st, int en, int node, int index, int dif){
    if(st > index || en < index) return;
    tree[node] += dif;
    if(st == en) return;
    int mid = (st + en) / 2;
    update(st, mid, node*2, index, dif);
    updqte(st, mid+1, node*2+1, index, dif);

}

 

 

#include<iostream>
#include<cmath>
#define SIZE 1000000

using namespace std;
typedef long long ll;

int N;
int arr[SIZE];
ll tree[4*SIZE];

int init(int st, int en, int node){
    if(st == en) return tree[node] = arr[st];
    int mid = (st + en) / 2;
    return tree[node] = init(st, mid, node * 2) + init(mid+1, en, node*2+1);
}



ll segtreeSum(int st, int en, int node, int left, int right){
    if(st > right || en < left) return 0;
    if(en <= right && st >= left) return tree[node];
    int mid = (st + en) / 2;
    return segtreeSum(st, mid, node*2, left, right) + segtreeSum(mid+1, en, node*2+1, left, right);
}

int main(void){
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);

    cin >> N;
    for(int i=0; i<N; i++) cin >> arr[i];
    init(0, N-1, 1);
    int treesiz = 1 << ((int)ceil(log2(N)) + 1);
    cout << treesiz << "\n";
    for(int i=1; i<= treesiz; i++) cout << i << ":" << tree[i] << "\n";
}

입력: 7

2 1 7 3 4 2 5