세그먼트 트리(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번: 구간 합 구하기

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄

www.acmicpc.net

 

#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;
}​
사업자 정보 표시
원당컴퓨터학원 | 기희경 | 인천 서구 당하동 1028-2 장원프라자 502호 | 사업자 등록번호 : 301-96-83080 | TEL : 032-565-5497 | Mail : icon001@naver.com | 사이버몰의 이용약관 바로가기
  1. Favicon of http://pangyione.com/ BlogIcon 청결원 2021.11.27 07:22

    포스팅 잘 보고 가네요
    즐겁고 행복한 주말 보내세요~

  2. 핑구야날자 2021.11.27 07:46

    트리구조를 잘 이해하면 코딩하는 실력도 많이 늦을 거 같아요

  3. Favicon of https://xuronghao.tistory.com BlogIcon 空空(공공) 2021.11.27 09:17 신고

    세그먼트 트리 알아갑니다^^

  4. Favicon of https://invitetour.tistory.com BlogIcon 휴식같은 친구 2021.11.27 11:15 신고

    너무 전문적인 내용이네요.ㅎ
    즐거운 주말 보내세요.

  5. Favicon of https://seunmi1981.tistory.com BlogIcon 구름 달빛 2021.11.27 15:42 신고

    잘보고가요 즐거운 하루 되세요

  6. Favicon of https://lovedde.tistory.com BlogIcon 모란들꽃 2021.11.27 18:02 신고

    안녕하세요
    포스팅 잘보고갑니다
    편안한 주말 보내세요 ^^

  7. Favicon of https://jsalang.tistory.com BlogIcon 추억거리 2021.11.27 21:57 신고

    와우~~ 평소에 어려운 용어는
    나름 알아가려고 열심히 읽는데
    이 포스팅 은 정말 그림을
    보는듯해요. 진짜 전문적인
    지식이네요
    멋있으세요. 이런 전문적인 지식을
    나눠주셔서 어렵지만 조금은 배워가요.
    용어는 외워볼게요 ㅎ ㅎ
    남은 주말도 행복하게 보내세요

  8. Favicon of https://arimarim.tistory.com BlogIcon 사랑스love 2021.11.28 07:56 신고

    알아두면 좋긴할텐데
    저는 평생 쓸 일이 없을거 같아요 ㅎㅎ

  9. Favicon of https://itadventure.tistory.com BlogIcon CrayFall 2021.11.28 15:06 신고

    정렬 알고리즘 중에 꽤 난이도 있는 건데 깔끔한 코드로 멋지게 구현하셨네요:) 잘 보고 갑니다~

  10. Favicon of https://kbh6628.tistory.com BlogIcon 청산사랑 2021.11.28 15:51 신고

    좋은정보 포스팅 잘보았습니다
    행복은 찾아오는것이 아니라
    늘 주위에 머무는 것이랍니다!
    늘 웃음이 함께하는 행복 가득한
    하루 되시길 바랍니다~♬

  11. Favicon of https://dhksabaha.tistory.com BlogIcon ♡하늘새♡ 2021.11.28 21:22 신고

    구독하여
    좋은 정보 간직합니다
    소중한 이웃으로 함께 성장해요
    감사합니다^^/

  12. Favicon of http://pangyione.com/ BlogIcon 청결원 2021.11.29 06:36

    포스팅 잘 보고 가네요
    한주 좋은 하루 시작 보내세요~

  13. Favicon of https://heysukim114.tistory.com BlogIcon *저녁노을* 2021.11.29 06:48 신고

    어렵네요.ㅎㅎ

    즐거운 한 주 되세요

  14. Favicon of https://memoryseung1224.tistory.com BlogIcon 청두꺼비 2021.11.29 08:43 신고

    좋은 정보 감사합니다. 덕분에 잘 알고 가요 . :)

  15. Favicon of https://kkabul10.tistory.com BlogIcon 푸른하늘은하수 2021.11.29 10:35 신고

    ㅋ 저에게는 한없이 어렵군요~~ 잘 보고 갑니다~^^

+ Recent posts