SEGMENT TREE

개요

segment tree 자료구조를 공부하고 정리한다.

공부하게 된 배경

백준 1168 문제를 O(n^2)방법으로 풀었는데 시간초과가 발생하여
더 좋은 풀이 방법을 찾지 못하던 중
찾아보니 segment tree를 이용하면 O(NlogN)으로 풀 수 있다는 것을 발견하고
segment tree를 알아보게 되었다.

segment tree 개요

segment tree는 일반적으로 트리 자체에 구간합을 가지고 있다.
루트가 모든 합, 루트의 왼쪽에는 0~N/2까지,
루트의 오른쪽은 N/2+1 ~ N-1까지의 구간 합을 가지는 식으로 트리가 구성된다.
트리의 특징 상 필요한 합을 탐색하는데 시간복잡도는 O(logn)으로 선형적 자료구조에서 보다 빠름을 알 수 있다.

segement tree 코드

#include <iostream>
using namespace std;
const int MAX = 10001;
int arr[MAX];
int N;
int tree[MAX];

void init()
{
    cin >> N;
    for(int i=0;i<N;i++)
    {
        cin >> arr[i];
    }
}

int makeSegmentTree(int start,int end,int node)
{
    if(start == end)
    {
        return tree[node] = arr[node];
    }
    int mid = (start+mid)/2;
    return tree[node] = makeSegmentTree(start,mid,node * 2) + makeSegmentTree(mid+1,end,node * 2 + 1);

}

int sumSegmentTree(int start,int end,int node,int left,int right)
{
    if(left > end || right < start)
    {
        return 0;
    }
    //구간에 충족한다면 더 들어갈 필요 없이 리턴  
    if(left <= start && end <= right)
    {
        return tree[node];
    }
    int mid = (start + end)/2;
    return sumSegmentTree(start,mid,node*2,left,right) + sumSegmentTree(mid+1,end,node*2+1,left,right);
}

void updateSegmentTree(int start,int end,int node,int changeVal,int idx)
{
    if(start > idx || end < idx)
    {
        return;
    }
    tree[node] += changeVal;
    //마지막 구간을 업데이트 하고 나면 더 깊게 들어갈 필요 없이 리턴
    if(start == end)
    {
        return;
    }
    int mid = (start + end) / 2;
    updateSegmentTree(start,mid,node*2,changeVal,idx);
    updateSegmentTree(mid+1,end,node*2+1,changeVal,idx);
}

int main()
{
    init();
    makeSegmentTree(0,N-1,1);

}