[ 세그먼트 트리(Segment Tree) ] 개념과 구현방법 (C++)

이번 글에서는 세그먼트 트리(Segment Tree) 에 대해서 이야기를 해보자.

1. 세그먼트 트리 ( Segment Tree ) ??

가장 먼저, 세그먼트 트리가 무엇을 하기 위한 놈인지 부터 알아보자.

세그먼트 트리는 "구간을 저장하기 위한 트리" 이다. 예를 들어서 5칸 짜리 배열이 있다고 가정해보자.

int Array[5] = { 1, 2, 3, 4, 5 } 이런 배열이 존재한다고 가정해보자.

그럼 여기서 "2번째 값 부터 4번째 값 까지의 합이 얼마일까?" 라고 묻는다면, 우리는 2 + 3 + 4 를 계산하게 된다.

또, "1번째 값 부터 5번째 값 까지의 합이 얼마일까?" 라고 묻는다면, 다시 한번 1 + 2 + 3 + 4 + 5 를 계산하게 될 것이다.

위와 같이 '주어진 전체에서, 특정 구간에 대한 연산을 묻는 경우' 만 본다면, 특별한 자료구조를 사용하는 것 보다는 처음에

모든 합을 다 구해놓고 계산하는 방식을 생각할 수 있다. 이렇게, "특정 구간에 대한 합을 묻는 연산"을 '1번 연산' 이라고 표현

해보자. 이제부터는 위의 경우에서 한 가지 연산을 더 진행해보자.

"2번 째 값을 '7'로 바꾸세요." 이런 연산이 추가되었다.

너무나도 간단한 문제이다. { 1, 2, 3, 4, 5 } 를 { 1, 7, 3, 4, 5 } 로 바꿔주면 된다. 이렇게, "특정 값을 바꾸는 연산"을 '2번 연산' 이라고 표현해보자. 이 후에 위와 같이 "2번째 값부터 4번째 값 까지의 합을 구하세요 ~", "3번째 값부터 5번째 값 까지의 합을 구하세요 ~",  "4번째 값을 '6'으로 바꾸세요 ~" 와 같은 연산들이 쭉 이어진다고 생각해보자. 아직까지는 별 문제 없을 거라 느낄 수 있다.

그럼 1번연산과 2번연산에 대해서 조금 더 구체적으로 생각해보자.

N칸 짜리 배열이 있다. 1번과 2번 연산은 합쳐서 최대 M번 주어진다고 가정해보자.

우리는 1번 연산을 진행하는데 걸리는 시간은 O(N) 만큼의 시간이 소요될 수 있고, 2번 연산을 진행하는데 걸리는 시간은 O(1) 만큼

소요될 수 있다. 결과적으로 2개의 연산을 모두 진행하는데 걸리는 시간은 O(NM) 만큼의 시간복잡도를 갖게 된다.

즉, N값과 M값이 매우 큰 값이 들어올 경우에는 생각보다 간단한 연산이라고 생각했음에도 굉장히 시간이 오래 걸리게 된다.

이런 경우 '세그먼트 트리'를 사용하게 되면 O(logN) 만큼의 시간만으로 굉장히 효율적으로 해결할 수 있다.

세그먼트 트리의 전체적인 구조를 간단하게 표현하면 다음과 같은 형태로 이루어져 있다.

위의 그림에서 각 노드들 안에 적혀있는 숫자들은 배열의 Index번호를 의미한다.

밑에서 더 구체적으로 알아보겠지만, 맛보기로 이야기하자면, 리프노드(자식이 없는 노드)들은 배열의 값을 그대로 가지고 있는

형태이고, 그게 아닌 노드들은 자식 노드들이 가지는 값들에 대한 연산 결과를 저장하고 있는 형태이다.

예를 들어서 각 구간에 대한 합을 구하기 위해서 세그먼트 트리를 만들었다면, '0-1', '2-3' 과 같이, a-b 의 형태로 적혀있는

노드들이 갖는 의미는 a번 Index부터 b번 Index까지의 합을 나타내고 있는 것이다.

즉, 루트노드는 전체 구간에 대한 합을 가지고 있게 되는 것이다. 무슨말인지 몰라도 좋다. 지금부터 이 세그먼트 트리에 대해서

구체적으로 알아보자.

2. 세그먼트 트리(Segment Tree) 생성과정

그럼 세그먼트 트리를 직접 구현하기 전에 ! 어떻게 구현하는지, 크기는 어떻게 설정하는지, 어떤 구조로 만드는지 알아보자.

간단하게 Arr[] = { 1, 2, 3, 4, 5 } 라는 값을 가지는 크기가 5칸 짜리인 배열을 가지고 알아보자.

그리고 지금부터 이 글의 끝까지, { 1, 2, 3, 4, 5 } 라는 배열에 대한 '1번연산'과 '2번연산' 을 진행해보자.

먼저, 이름에서부터 알 수 있듯이, 세그먼트 트리는 자료구조 '트리'의 형태를 갖추고 있다. 트리 중에서도 '이진트리'의 모습을

가진 구조이다. 우리는 지금부터 세그먼트 트리를 만들 것인데, 이런 구조로 만들 것이다.

"리프노드(자식이 없는 가장 말단노드) 는 배열의 값 그 자체를, 그게 아닌 노드에는 해당 자식들의 합을 저장" 하는 형태이다.

{ 1, 2, 3, 4, 5 } 에 대한 세그먼트 트리의 결과부터 보여주자면 다음과 같다.

위의 그림이 세그먼트 트리이다. 보면, 리프노드(자식이 없는 노드) 들은(파랑색 원), 배열 { 1, 2, 3, 4, 5 } 의 값을 그대로 가지고

있다. 하지만, 리프노드가 아닌 다른 노드들을 보게되면, 이상한 숫자들이 적혀있다. 해당 숫자들이 갖는 의미는 "자식 노드들의 합"

이 된다. 루트노드부터 하나씩 값을 알아보자. 루트노드는 '15'라는 값을 가지고 있다. '15'라는 값은 왼쪽 자식인 '6'과 오른쪽 자식인 '9'의 합으로 인해서 생성된 값이다. 그럼 왼쪽 자식인 '6'을 보게되면, '3'과 '3'의 합으로 이루어져있다. 그 중, 오른쪽 자식은

리프노드로써, 배열의 3번째 값인 '3'을 나타내고 있다. 그리고 왼쪽 자식인 '3'을 보게되면, '1'과 '2'의 합으로 생성된 값을

나타내고 있으며, '1'과 '2'는 리프노드로써 더 이상의 자식을 가지고 있지 않다.

다시 루트노드에서 오른쪽 자식으로 오게되면 '9'라는 값을 가지고 있는데 이 '9'는 '4'와 '5'의 합으로 인해서 생성된 숫자이고

'4'와 '5'는 리프노드로써 배열의 값을 그대로 가지고 있다.

즉, '15'라는 값은, 모든 자식의 합, 다시 말해서 "모든 구간의 합"을 나타내는 숫자이다. 실제로, 1 + 2 + 3 + 4 + 5 를 하게되면

15가 나오게 된다. 이런식의 트리를 지금부터 만들어 볼 것이다.

그럼 세그먼트 트리의 크기부터 설정해보자. 위의 배열 5개에 대한 세그먼트 트리를 통해서 알아 낼 수 있는 정보들을

모두 알아보자.

1. 5개에 대한 세그먼트 트리를 구현하는데 필요한 노드의 수는 9개이다.

2. 트리의 높이가 3이다.

이 정도말고는 더 알아볼 만한 정보는 없는 것 같다.

그럼 세그먼트 트리는 이진 트리의 형태를 가지고 있다고 했으니, 2의 제곱꼴로 표현되는 크기의 배열을 생각해보자.

예를 들어서 { 1, 2, 3, 4 } 이렇게 크기가 4인 배열이 있다고 가정해보자. 이 배열에 대한 세그먼트 트리는 어떻게 나올까?

위와 같은 형태로 나오게 될 것이다. 위의 세그먼트 트리는 노드가 7개이고, 높이가 2인 이진트리의 형태를 갖추고 있다.

트리의 높이 라는 것은 노드의 갯수만으로 파악할 수 있다. 바로, log2(N) 으로 구할 수가 있다.

조금 더 정확하게 표현해보자면 ceil(log2(N)) 으로 표현할 수 있다. 여기서 'ceil(x)' 는 무조건 반올림을 시켜주는 함수이다.

N = 4일 경우, log2(4) = 2.000 이고, 이 경우에는 뒤에 소수점이 없는 것과 동일하므로 ceil(log2(4)) = 2 가 된다.

N = 5일 경우, log2(5) = 2.xxxx 이고, 이 경우에는 소수점이 붙는데, 해당 소수점이 0.5보다 크든 작든 상관없이 무조건

반올림을 하게 된다. 즉, ceil(log2(5)) = 3 이 된다.

실제로 위에서 5칸짜리 배열을 세그먼트 트리 구조로 표현한 그림을 다시 한번 보게되면, 높이가 3이 된다.

4칸짜리 배열을 세그먼트 트리 구조로 표현한 그림을 보게 되면, 높이가 2인 트리가 그려져 있는 것을 확인할 수 있다.

하지만 ! 정작 우리가 구하고자 하는 트리의 크기는 구하지 못했다. 높이만 구했을 뿐이다.

세그먼트 트리를 구현하기 위해서 필요한 크기는 2 ^ (높이 + 1) 을 한 값 만큼 필요하게 된다.

N = 4일 때, 높이가 2인 세그먼트 트리에는 노드가 총 7개가 존재했다. 위의 공식에 대입해보면 2 ^ (2 + 1) = 2 ^ 3 = 8

실제 노드는 7개인데, 왜 공식에 의해서 나오는 값은 8일까 ?? 사실 실제 노드도 8개가 존재한다. 그런데 ! 하나의 노드를 사용하지

않는다. 배열이든 벡터이든 0번째 Index를 사용하지 않는다. 왜 ?? 트리의 자식과 부모 관계를 계산하는데 있어서

복잡해지기 때문이다. 부모노드번호 x 2 = 왼쪽자식노드번호, 부모노드번호 x 2 + 1 = 오른쪽자식노드번호

이게 이진트리에서 일반적으로 사용하는 부모와 자식 관계를 표현하는 방식이다. 그런데 0번 Index를 사용하는 순간, 위의

방식이 깨져버리기 때문이다. 그래서 우리는 1번 노드부터 사용할 것이다.

그렇게 되면 위의 공식에서는 '8개의 노드가 필요' 하다고 나왔지만, 0번 Index를 빼버리면 총 '7개의 노드'를 사용하는

것이고, 실제로 필요한 노드도 7개가 된다.

N = 5일 때 한번만 더 계산을 해보자. 먼저 N = 5일 때, 트리의 높이 = ceil(log2(5)) = 2.xxxx = 3 이 되었다.

필요한 크기는 2 ^ (3 + 1) = 2 ^ 4 = 16칸이다. 실제로, 그림을 보게되면 총 9개의 노드가 사용되었고, 16칸 까지는 필요가 없다.

하지만 ! 주어진 N에 따라서 딱 맞게 칸을 생성해주기가 힘들다. 왜냐하면, ceil(log2(N)) = x 라는 값이 나왔다고 가정했을 때,

이 'x'는 2의 거듭제곱꼴에 의해서 딱 맞게 나온 x일 수도 있고, 그게 아니라 더 작은 숫자인데 반올림을 해서 나온 x일 수도 있다.

이 때, 가장 많은 칸이 필요한 경우는 2의 거듭제곱꼴에 의해서 딱 맞게 나온 x일 것이고, 그 때 필요한 칸을 기준으로

공간을 할당해 준다.

위의 과정을 깔끔한 공식으로 정리를 해보면 다음과 같이 표현할 수 있다. 트리의 높이가 H일 때,

세그먼트 트리의 크기 = 1 << (H + 1)

정리를 하자면 다음과 같다.

크기가 N인 배열이 존재할 때

1. 트리의 높이 = ceil(log2(N))

2. 세그먼트 트리의 크기 = (1 << (트리의 높이 + 1) )

세그먼트 트리의 크기에 대해서 한 가지만 더 이야기해보자면, 위에서 본인이 말했듯이, 트리의 높이를 구하고 ~ 세그먼트 트리의

크기를 구한다 ~ 라는 이런 복잡한(?) 과정 없이 깔끔하게 배열의 크기 x 4 를 한 값을 세그먼트 트리의 크기로 설정하시는

분들도 굉장히 많이 있다. 배열의 크기 x 4를 한 값은, 위에서 말한 세그먼트 트리의 크기를 구하는 값보다 항상 더 큰 값이

나오게 된다. 물론, 메모리의 낭비가 조금 더 있을 수는 있지만, 정말 간단하게 세그먼트 트리의 크기 = 주어진 배열의 크기 x 4

로 설정하고 진행해도 무방하다.

3. 세그먼트 트리 만들기

이제 세그먼트 트리가 뭘 하는 자료구조인지, 얼마의 크기를 갖추고 있는지까지 알아봤으니 이제 직접 값을 대입해보자.

본인 같은 경우는 보통 벡터를 하나 선언해서 세그먼트 트리로 만들어 준다.

벡터의 크기는 위에서 말한 공식으로 초기 크기를 할당해준 후 시작한다.

세그먼트 트리를 만들 때는 재귀를 사용해서 만들어준다. 재귀에 사용되는 매개변수로는 다음과 같이 3개의 변수가 있다.

{ 현재 노드 번호 , 시작 범위 , 마지막 범위 }

위에서도 말했듯이 우리는 0번 인덱스를 사용하지 않고, 1번 인덱스부터 사용할 것이기 때문에 가장 초기에 호출되는

현재노드번호 = 1 로 호출될 것이다.

시작범위는 배열의 시작범위이다.즉 '0'을 의미한다.

마지막범위는 배열의 마지막범위이다. 즉, 'N - 1'을 의미한다.

[ 1, 0 , N - 1 ] 로 첫 호출을 시작한다.

지금부터 다시 { 1, 2, 3, 4, 5 } 라는 5개의 배열을 세그먼트 트리로 만드는 과정을 알아보자.

과정을 먼저 크기 적어보고 시작하자면 다음과 같다.

1. 주어진 범위를 반으로 나눈다.

2. 나눠진 2개의 범위에 대해서 '왼쪽범위'에 대한 재귀호출을 한다.

3. 나눠진 2개의 범위에 대해서 '오른쪽범위'에 대한 재귀호출을 한다.

4. 위의 과정을 반복한다.

이진트리로 이루어져 있기 때문에, 항상 범위를 반으로 나누는 것이 중요하다.

그럼 위의 범위를 반으로 나눠보자. 중간값은 = (0 + N - 1) / 2 = (0 + 4) / 2 = 2 가 된다.

즉, 우리는 0 ~ N - 1로 설정되어 있는 범위를 0 ~ 2와, 3 ~ 4로 나눠서 구현할 것이다.

시작점 ~ 끝점 으로 이루어져 있던 범위를, 시작점 ~ 중간점, 중간점 + 1 ~ 끝점

이렇게 2개의 범위로 나눈다고 생각하면 된다. 해당 범위를 토대로 재귀를 호출해보자.

그런데 ! 노드 번호는 어떻게 바뀔까 ?? 왼쪽 노드로 가게되면, 현재 노드 x 2 의 번호를 가지게 될 것이고,

오른쪽 노드로 가게되면 현재 노드 x 2 + 1 의 번호를 가지게 될 것이다.

나눠진 2개의 범위에 대해서 '왼쪽범위' 에 대한 재귀호출을 진행해보자.

아마 재귀는 [ 2 , 0 , 2 ] 로 호출이 될 것이다.

그 안에서 다시 1번과정이 반복되어진다. 범위를 2개로 나누게 되면 0 ~ 1, 2 ~ 2 로 나뉘게 된다.

나눠진 2개의 범위에 대해서 '왼쪽범위' 에 대해서 재귀호출을 또 진행해보자.

아마 재귀는 [ 4 , 0 , 1 ] 로 호출이 될 것이다. 또 반복하자. 그렇게되면, [ 8 , 0,  0 ] 으로 호출이 된다.

언제까지 이렇게 나눠야할까 ?? 바로 지금이다 !

이 재귀함수에서 기저조건에 해당하는 부분이다. 바로 '시작하는 범위 = 끝나는 범위' 일 경우, 재귀는 종료된다.

종료하기 전에 값을 반드시 설정해 줘야 한다. 바로 SegmentTree[노드번호] = 배열[시작범위] 이런식으로 !

시작하는 범위 = 끝나는 범위 라는 것이 의미하는 것은 더 이상 나눌 수 있는 범위가 없다라는 것이고, 이는 더 이상의

자식을 가질 수 없음을 의미한다. 즉, 리프노드라는 것을 의미하고 위에서도 말했듯이, 리프노드는 배열의 값을 그대로 가지게

된다. 따라서, 해당 노드에는 배열의 값을 그대로 저장해 주는 것과 동시에 종료시켜 주면 된다.

[ 4 , 0 , 1 ] 에서 우리는 왼쪽범위인 [ 8 , 0 , 0 ] 으로 온 상태이다. 이게 끝난다면, 오른쪽범위를 체크하러 갈 것이다.

오른쪽범위는 [ 9, 1, 1 ] 이 될 것이다. 마찬가지로 '시작범위 = 끝나는 범위' 이므로, 그대로 값을 설정해준다.

SegmentTree[9] = Arr[1].

그럼 이렇게 되면 우리는 노드 4번의 값 또한 구할 수 있다. 바로, 8번과 9번 노드의 값을 구했으니, 이 2노드의 값을 더해주면

되는 것이다. 이게 재귀가 무자비하게 반복되다 보니, 굉장히 헷갈리는데 현재의 상태를 그림으로 나타내면 이렇게 볼 수 있다.

위의 상태와 같다고 볼 수 있다. 너무 그림에 신경쓰지는 말고, 재귀가 어떻게 돌아가는지만 생각을 하자.

우리는 지금 [ 4, 0, 1 ] 에서 호출할 수 있는 재귀를 모두 호출 후, 4번 노드의 값 까지 구한 상태이다.

위의 재귀가 끝난다면 [ 5, 1, 1 ] 로 갈 것이다. 이 경우 바로 '시작범위 = 끝 범위' 이므로, 노드 5번의 값이 Arr[2] 로 설정될

것이다. 5번 노드의 값이 설정되면서 동시에 2번 노드의 값이 결정되었다. 바로 4번노드 + 5번 노드를 한 값이다.

이 후, 2번 노드의 값이 설정되었으면 해당 재귀 호출이 모두 끝난다는 것을 의미하고, 이제 [ 3, 3, 4 ] 로 넘어가보자.

[ 3, 3, 4 ] 는 [ 6, 3,  3] 과 [ 7, 4, 4 ]를 호출 하게 된다. 여기서 6번 노드와 7번 노드의 값이 구해질 것이고,

이 값들에 의해서 3번 노드의 값이 구해질 것이다. 3번 노드의 값이 구해짐에 따라서 2번 노드 + 3번 노드를 한 값이

1번 노드의 값이 됨으로써 세그먼트 트리가 완성된다. 재귀의 과정을 마무리해보면 다음과 같다.

위와 같은 형태로 표현이 될 것이다 ! 이런식으로 세그먼트 트리가 생성되어진다. 해당 부분을 코드로 한번 확인해보자.

int Make_SegmentTree(int Node, int Start, int End)
{
    if (Start == End) return SegmentTree[Node] = Arr[Start];
    
    int Mid = (Start + End) / 2;
    int Left_Result = Make_SegmentTree(Node * 2, Start, Mid);
    int Right_Result = Make_SegmentTree(Node * 2 + 1, Mid + 1, End);
    SegmentTree[Node] = Left_Result + Right_Result;
 
    return SegmentTree[Node];
}
 
int main(void)
{
    int Tree_Height = (int)ceil(log2(N));
    int Tree_Size = (1 << (Tree_Height + 1));
    SegmentTree.resize(Tree_Size);
    Make_SegmentTree(1, 0, N - 1);
}

위의 코드에서 line 15 ~ 18은 세그먼트 트리의 초기 크기를 설정하는 과정이다.

line3 ~ 10이 실제로 세그먼트 트리를 만드는 과정이다.

line3) 은 재귀의 종료 조건이다. 바로, "시작범위 = 끝 범위" 인 경우이다. 해당 경우에는, 세그먼트 트리에 해당 배열의 값을

설정해주고 그 값을 return 시켜버린다.

line5) 는 범위를 2개의 범위로 나누기 위해서 '중간값'을 구하는 과정이다.

line6) 에서는 범위 중에서 '왼쪽범위(노드번호 = 노드번호 x 2)'

line7) 에서는 범위 중에서 '오른쪽범위(노드번호 = 노드번호 x 2 + 1)' 을 호출하는 것이다.

line8) 에서는 '왼쪽범위'와 '오른쪽범위' 를 탐색하면서 구한 값들을 저장하는 과정이다. 이후 해당 값을 return 해준다.

4. 세그먼트 트리 1번연산 (구간합 구하기)

우리가 위에서 열심히 만든 Arr[] = { 1, 2, 3, 4, 5 } 에 대한 세그먼트 트리이다.

여기서 "2번째 값부터 3번째 값 까지의 합을 구하세요" , "3번째값부터 5번째 값 까지의 합을 구하세요" 라는 연산이 주어졌다고

생각해보자. 우리는 위의 세그먼트 트리를 통해서 굉장히 빠르고 간단하게 구할 수 있다.

우리가 탐색을 할 때에는 크게 3가지 경우로 나눠서 생각할 수 있다.

1. 현재 우리가 탐색하는 범위가, 우리가 찾고자 하는 구간과 완전히 겹쳐지지 않는 경우.

2. 현재 우리가 탐색하는 범위가, 우리가 찾고자 하는 구간에 완전히 속해있는 경우.

3. 1, 2번 경우를 제외한 나머지 경우. 즉, 일부만 걸쳐있는 경우.

1번 같은 경우에는 다음과 같은 경우이다. 우리에게 제시된 연산이 "배열의 1번째 값부터 3번째 값 까지의 합을 구하세요" 라고

주어지게 된다면 우리는 세그먼트 트리의 1번 노드에서부터 범위를 2개로 나눠가면서 왼쪽 범위에 대한 탐색, 오른쪽 범위에

대한 탐색을 진행할 것이다.

이 때, 오른쪽 범위로 온 경우를 보자. 노드 번호는 '3'번일 것이고, 범위는 '3 ~ 4' 로 호출된 상태일 것이다.(위의 재귀그림 참고)

그런데, 배열의 첫 번째 값부터 3번째 값 까지는 사실상 0번 Index ~ 2번 Index까지의 합을 구하라는 것을 의미한다.

이 때, 3번 Index와 4번 Index에 대한 계산을 해놓은, 3번 Node에 대해서 더 이상의 탐색이 필요할까 ??

더 깊은 탐색을 해봤자 우리가 원하는 값은 나오지 않을 것이다. 즉, 더 이상의 탐색이 필요 없다.

2번 같은 경우는 다음과 같은 경우이다. 첫 번째 값부터 세번째 값 까지의 합을 구하라고 했는데, 2번 노드로 온 경우이다.

위의 그림에서 빨강색 글씨는 '노드번호' 를 의미한다.

여기서 2번 노드라는 것은 '6'의 값을 가진 노드를 의미하고, 이 '6'은 배열의 0번 Index ~ 2번 Index까지의 구간을 포함하고 있는

노드이다. 이 경우에는, "우리가 탐색하고 있는 범위가, 우리가 구하고자 하는 범위에 완전히 속해 있다" 라고 말할 수 있고,

더 이상의 탐색을 하지 않고 그대로 그 Node의 값을 return 시켜주면 된다. 즉, 우리는 바로 '6'이라는 값을 구할 수 있는 것이다.

3번 경우는 일부만 걸친 경우를 의미한다.

예를들어서 "배열의 3번째 값 부터 4번째 값 까지의 합을 구하세요" 라는 연산이 주어졌다고 생각하자.

물론, 실제로 배열에서는 2번 Index부터 3번 Index까지의 합을 구해야 하는 것이다.

이 때, 2번 노드(6의 값을 가진 노드) 로 왔다고 생각해보자. 2번 노드가 포함하고 있는 범위는 배열의 "0번 Index ~ 2번 Index"의

값들을 포함하고 있다. 그런데 우리는 "2번 Index ~ 3번 Index"까지의 합을 구해야 하는 것이다.

이런 경우, "우리가 탐색하고 있는 범위가, 우리가 구하고자 하는 범위와 일부가 걸쳐있다" 라고 말할 수 있고,

이 경우에는 마찬가지로 왼쪽자식과 오른쪽 자식으로 더 깊은 탐색을 진행해야 한다.

이 부분을 코드로 알아보자.

int Sum(int Node, int Start, int End, int Left, int Right)
{
    if (Left > End || Right < Start) return 0;
    if (Left <= Start && End <= Right) return SegmentTree[Node];
 
    int Mid = (Start + End) / 2;
    int Left_Result = Sum(Node * 2, Start, Mid, Left, Right);
    int Right_Result = Sum(Node * 2 + 1, Mid + 1, End, Left, Right);
    return Left_Result + Right_Result;
}

이게 구간합을 구하는 코드이다. 매개변수의 뜻부터 알아보자.

Node = 노드 번호

Start , End = 해당 노드가 포함하고 있는 범위

Left, Right = 우리가 구하고자 하는 범위

line3) 은 1번 경우를 의미한다. 현재 탐색하고 있는 범위가 우리가 구하고자 하는 범위와 완전히 일치하지 않는 경우이다.

이 경우, 더 이상의 탐색은 무의미하다. 따라서 그대로 0을 return.

line4) 는 2번 경우를 의미한다. 현재 탐색하고 있는 범위가 우리가 구하고자 하는 범위에 완전히 속해있는 경우이다.

이런 경우에는 더 깊은 탐색을 해볼 필요도 없이 해당 노드의 값을 그대로 가져오기만 하면 된다.

line 6 ~ 9) 는 3번 경우를 의미한다. 일부만 걸쳤으므로 더 깊은 탐색을 진행해봐야 하는 경우이다.

마찬가지로, 왼쪽범위에 대한 탐색, 오른쪽범위에 대한 탐색을 진행 후, 그 합을 return 시켜주면 "구간합"을 구할 수 있다.

5. 세그먼트 트리 2번 연산 (값 바꾸기)

배열에서는 특정 Index의 값을 바꾸라고 하면 너무나도 간단하게 바뀌었지만, 세그먼트 트리에서는 그럴 수가 없다.

왜냐하면, 구간에 따른 연산 결과를 저장해 놓은 트리인데, 여기서 하나의 값이 바뀌게 되면, 그 값에 영향을 끼치는 모든 노드들의

값을 바꿔줘야 하기 때문이다. 지금부터는 이 과정을 알아보자.

우리는 먼저 크게 2가지의 경우로 나눠서 생각할 수 있다.

1. 바꾸고자 하는 Index값이, 현재 우리가 탐색하는 범위내에 속해있는 경우.

2. 바꾸고자 하는 Index값이, 현재 우리가 탐색하는 범위내에 속해있지 않은 경우.

2번 같은 경우에는 더 이상의 탐색을 하지 않아도 된다. 왜냐하면 어차피 우리가 원하는 Index는 탐색하고 있는 범위 내에

속해있지 않은데, 자식노드로 더 깊게 들어간다고 해서 해당 Index가 갑자기 나올 수 있을까 ? 절대 그렇지 않다.

따라서 2번 같은 경우는 그대로 탐색을 종료해버리면 된다.

그럼 1번의 경우를 생각해보자. 우리가 사용하는 배열(Arr[] = { 1, 2, 3, 4, 5 }) 에서 "2번째 값을 5로 바꾸세요 !" 라는 연산이

주어졌다고 생각해보자. 2번째 값이라는 것은 배열에서는 '1번 Index'를 의미한다.

우리는 어느 때와 똑같이 1번 노드에서 부터 탐색을 시작할 것이다. 1번노드에서, 2번 노드와 3번 노드로 갈 것이다.

그런데 3번 노드를 보자. 3번 노드는 (3번 Index ~ 4번 Index)에 대한 정보를 가지고 있는 노드이다. 1번 Index가 완전히 속해있지

않은 경우이다. 이 경우에는 ? 굳이 6, 7번 노드 까지 들어가볼 필요 없이 그대로 탐색을 종료해주면 된다.

그럼 2번 노드를 보자. 2번 노드는 (0번 ~ 2번Index)에 대한 정보를 가지고 있는 노드이고, 우리가 찾는 Index가 해당 범위에

속해있으니, 값을 바꿔줘야 한다. 왜 ?! 우리가 찾고자 하는 Index에 대한 정보를 포함하고 있는 노드이기 때문에,

우리가 찾고자 하는 Index의 값을 바꾸게 되면, 이 노드 역시 값이 바뀌게 될 것이다. 따라서, 값을 바꿔주는 것이다.

어떻게 ? 우리는 Arr[1] = 2 의 값을 '5'로 바꾸고 싶어한다. 즉, +3만큼 연산을 하게 된다. 마찬가지로 2번 노드에도 + 3을

더해주면 되는 것이다. 그리고나서는 ?? 더 깊은 탐색을 진행해야 한다. 왜 ?? 해당 자식 노드들 중에서도 값이 바뀌는

노드들이 분명히 있을 것이기 때문에 그 노드들의 값 또한 변경해 주어야 하기 때문에 값을 바꿔준 후에 계속해서 탐색을

진행해주어야 한다.

그럼 4번노드와 5번 노드로 갈 것이다. 이 때 5번노드 ! 더 이상의 탐색이 필요없다 ! 왜냐하면 2번 Index에 대한 정보를 가지고

있는 노드이므로, 1번 Index를 찾고 있는 나와는 무관한 노드이다.

4번 노드는 0번 ~ 1번Index 에 대한 정보를 가지고 있는 노드이고, 우리가 찾고자 하는 Index가 이 안에 속해있다.

그럼 ? 값을 바꿔주고 또 자식탐색 !

그래서 어느덧 8번 노드까지 왔다. 8번 노드는 값을 바꿔줘야하나 ?? 8번 노드는 리프노드이고, 우리가 원하고자 하는 정보를

가진 노드가 아니다. 따라서 값을 바꿔줄 필요 없고 더 이상의 탐색 또한 할 필요가 없다. 왜 ? 자식이 없으니까 !

이 부분을 코드로 알아보자.

void Update_SegmentTree(int Node, int Start, int End, int Index, int Diff)
{
    if (Index < Start || Index > End) return;
    SegmentTree[Node] = SegmentTree[Node] + Diff;
 
    if (Start != End)
    {
        int Mid = (Start + End) / 2;
        Update_SegmentTree(Node * 2, Start, Mid, Index, Diff);
        Update_SegmentTree(Node * 2 + 1, Mid + 1, End, Index, Diff);
    }
}
 
int main(void)
{
    int Index = 1;
    int Value = 5;
    int Diff = Value - Arr[Index];
    Arr[Index] = Value;
    Update_SegmentTree(1, 0, N - 1, Index, Diff);
}

메인문에서 "1번 Index의 값을 5로 바꾸세요." 라는 명령이 떨어지고, 해당 값을 Update하는 과정이다.

line3) 에서 보면 "내가 찾고자 하는 Index가, 현재 탐색 범위와 완전히 다른 경우" 이다. 별다른 탐색 없이 return 시켜준다.

line4) 에서 보면, line3) 에서 return 되지 않고 오게 된 경우에만 실행되는 명령이다. line3) 에서 걸러지지 않았다는 것은,

내가 찾고자 하는 Index와 어느정도 겹치는 부분이 있다는 것을 의미하고, 값을 Update해줘야 한다.

line6) 에서 보면, 리프노드가 아니라면 계속해서 탐색을 진행해야 한다고 했다. 그 과정을 나타낸 것이다.

리프노드의 경우에는 더 이상의 자식이 없어서 탐색이 불가능하지만, 그게 아니라면 자식노드들 중에서도 값이 변하는

노드가 발생할 수 있기 때문에 반드시 탐색을 진행해 주어야 한다 !

지금까지 Segment Tree에 대해서 가장 보편적으로 알려져 있는 "구간합을 구하는 연산"과, "값을 변경하는 연산", 이 2가지

연산에 대해서 세그먼트 트리를 직접 구현해보고 연산과정을 이야기해 보았다.

본인도 굉장히 어렵다고 느꼈던 자료구조이고 부족한 점이 있을 수 있으니 이 점 참고하시고.. 많은 도움이 되었으면 좋겠습니다..