[자료구조]세그먼트트리(Segment Tree)

세그먼트 트리(Segment Tree)란?

- 주어진 쿼리에 대해 빠르게 응답하기 위해 만들어진 자료구조

- 구간 중에 Max,Min,Sum(최대,최소,구간의 합) 등을 빠르게 갱신할 수 있는 자료구조

 

세그먼트 트리(Segment Tree) 구현 목적

배열의 데이터 수  :  10개
배열의 데이터 A[10] = {1,2,3,4,5,6,7,8,9,10}
목적 : 구간에 대한 합 

예) 4번째 부터 6번째까지의(배열의 3번지부터 5번지까지의) 구간합은? 15

이러한 구간합을 구하는 가장 간단한 방법은 합을 미리 구해 놓고 1번째 부터 6번째의 합 21 에서 1번째 부터 3번째의 합 6을 빼면 15가 나온다.

1	2	3	4	5	6	7	8	9	10
1	3	6	10	15	21	28	36	45	55

 

하지만 각 데이터가 수시로 변경이 된다면?

만약 2번째 데이터가 2에서 3으로 변경 된다면 매번 다시 합을 구해야 한다.

이 데이터가 많다면? 합을 구하는 횟수가 많아진다.

 

따라서 이와 같이 데이터의 갱신이 많아 지는 경우 세그먼트 트리를 이용한다.

 

세그먼트 트리의 구현 방법

위와 같이 데이터가 입력이 들어 온다면 다음과 같은 트리 구조를 만들어 보자.(위치는 배열의 위치가 아닌 번째 데이터로 정의 하였음)

() 안의 수는 데이터를 담는 배열의 번지수이며 1번지는 데이터의 1번째 부터 10번째까지의 모든 합을 담는 배열이며 아래로 내려가면서 절반씩 나누어서 왼쪽과 오른쪽으로 할당하는 모습을 확인 할 수가 있다.

이때 자신의 왼쪽 자식은 자신의 번지 * 2 인것을 확인 할 수 있고 오른쪽 자식은 자신의 번지 * 2 + 1 인것을 확인할 수 있다.

또한 부모를 찾아 갈때는 자신의 번지 / 2 로 자신의 부모를 찾아 갈 수 있다.

위의 트리에서 처음 값은 모두 0으로 초기화 되어 있는 상태에서 1번째 데이터가 1이 업데이트 되는 경로를 찾아 보자.

위의 그림과 같이 1,2,4,8,16 번지를 업데이트 하게 된다.

이렇게 업데이트 하는 프로그램은 다음과 같이 구현이 가능하다.

void UpdateTree(int cur,int pos,long long val,int s,int e) ///cur:현재위치,pos:업데이트 할 위치,val:업데이트값,s:구간의 시작,e:구간의 끝 
{
    if(pos<s || e<pos) return; ///업데이트 하려는 위치가 구간을 벗어난 경우는 업데이트 필요 없다.
    if(s==e) ///업데이트할 position을 찾았다.
    {
        tree[cur]=val;
        return;
    }
    int m=(s+e)/2; ///중간값으로 나누어 왼쪽과 오른쪽으로 내려가 보자.
    UpdateTree(cur*2,pos,val,s,m);
    UpdateTree(cur*2+1,pos,val,m+1,e);
    tree[cur]=tree[cur*2]+tree[cur*2+1]; ///왼쪽 자식과 오른쪽 자식의 합이 자신의 값이다.
}

1번째 데이터를 1로 업데이트 하는 경우 를 확인하면 

UpdateTree(1,1,1,1,10) -> UpdateTree(2,1,1,1,5),UpdateTree(3,1,1,6,10) 을 호출하게 되고

UpdateTree(3,1,1,6,10) 은 범위를 벗어 나므로 더 이상 진행하지 않는다.

마찬가지로

UpdateTree(2,1,1,1,5) -> UpdateTree(4,1,1,1,3),UpdateTree(5,1,1,4,5) 을 호출하게 되고

UpdateTree(5,1,1,4,5)  은 범위를 벗어 나므로 더 이상 진행하지 않는다.

이렇게 반복하면서 내려 가다 보면

UpdateTree(8,1,1,1,1) 을 만나게 되고 여기서 위치를 찾게 되므로 tree[8]=1 을 갱신하고 빠져 나가면서 왼쪽 자식과 오른쪽 자식의 합을 구해 주면 업데이트가 완료 된다.

이때 N개의 데이터라고 하면 업데이트 시간은 logN 의 속도로 갱신을 할 수가 있다. 

이렇게 하면 구간합의 배열 값은 다음과 같이 갱신되어 있을 것이다.

여기서 4번째 부터 6번째까지의 합을 구하기 위해서는 다음의 합을 구하면 된다.

주황색의 위치 5번지와 24번지의 합 18 이 되는 것을 확인할 수 있다.

그렇다면 이러한 구간합을 구해 오는 쿼리를 살펴 보자.

long long Query(int cur,int searchstart,int searchend,int s,int e)
{
    if(e<searchstart || searchend<e) return 0; ///구간의 범위가 찾는 범위의 밖이라면 더 찾을 필요가 없다. 
    if(searchstart<=s && e<=searchend) return tree[cur]; ///구간의 범위가 찾는 범위 안쪽이면 해당 값을 리턴한다. 
    int m=(s+e)/2;
    long long num1=Query(cur*2,searchstart,searchend,s,m);
    long long num2=Query(cur*2+1,searchstart,searchend,m+1,e);
    return num1+num2;
}

Query(1,4,6,1,10) 을 호출하는 경우 동작하는 경로를 살펴 보면

Query(1,4,6,1,10) -> Query(2,4,6,1,5),Query(3,4,6,6,10) 을 호출하고

Query(2,4,6,1,5) -> Query(4,4,6,1,3),Query(5,4,6,4,5) 를 호출하고

Query(4,4,6,1,3)=> 구간이 찾으려고 하는 범위를 벗어나기 때문에 0을 리턴후 종료

Query(5,4,6,4,5)=> 구간이 찾으려고 하는 범위의 안쪽이기 때문에 5번지값 9를 리턴

Query(3,4,6,6,10)=> Query(6,4,6,6,8),Query(7,4,6,9,10)(범위밖으로 종료)

Query(6,4,6,6,8)=>Query(12,4,6,6,7),Query(13,4,6,8,8)(범위밖으로 종료)

Query(12,4,6,6,7)=>Query(24,4,6,6,6)(범위안에이므로 24번지값 리턴),Query(25,4,6,7,7)(범위 밖이므로 0 리턴)

위와 같이 찾아지는 것을 확인해 볼 수가 있다.

 

문제풀이

•https://www.acmicpc.net/problem/2042

2042번: 구간 합 구하기

 

#include <iostream>
#include <stdio.h>

using namespace std;
long long tree[1<<22];


void UpdateTree(int cur,int pos,long long val,int s,int e) ///cur:현재위치,pos:업데이트 할 위치,val:업데이트값,s:구간의 시작,e:구간의 끝
{
    if(pos<s || e<pos) return; ///업데이트 하려는 위치가 구간을 벗어난 경우는 업데이트 필요 없다.
    if(s==e) ///업데이트할 position을 찾았다.
    {
        tree[cur]=val;
        return;
    }
    int m=(s+e)/2; ///중간값으로 나누어 왼쪽과 오른쪽으로 내려가 보자.
    UpdateTree(cur*2,pos,val,s,m);
    UpdateTree(cur*2+1,pos,val,m+1,e);
    tree[cur]=tree[cur*2]+tree[cur*2+1]; ///왼쪽 자식과 오른쪽 자식의 합이 자신의 값이다.
}

long long Query(int cur,int s,int e,int searchstart,int searchend)
{
    if(searchend<s || e<searchstart) return 0;
    if(s<=searchstart && searchend<=e) return tree[cur];
    int m=(searchstart+searchend)/2;
    long long num1=Query(cur*2,s,e,searchstart,m);
    long long num2=Query(cur*2+1,s,e,m+1,searchend);
    return num1+num2;
}

int main()
{
    long long i,n,m,k;
    long long val,num,s,e,target;
    scanf("%lld%lld%lld",&n,&m,&k);
    m+=k;
    for(i=1;i<=n;i++)
    {
        scanf("%lld",&val);
        UpdateTree(1,i,val,1,n);
    }
    for(i=0;i<m;i++)
    {
        scanf("%lld",&num);
        if(num==1)
        {
            scanf("%lld%lld",&target,&val);
            UpdateTree(1,target,val,1,n);
        }
        else if(num==2)
        {
            scanf("%lld%lld",&s,&e);
            printf("%lld\n",Query(1,s,e,1,n));
        }
    }
    return 0;
}​