세그먼트 트리 (Segment Tree) 개념 정리

지난번에 문제풀이를 하면서, 세그먼트 트리를 활용할 일이 있어 오랜만에 개념을 공부했는데 기억이 잘 나지 않아서 한 번 정리해보려 합니다.

---

세그먼트 트리 (Segment Tree)의 정의!

우선 위키백과에서는 세그먼트 트리를 다음과 같이 정의하고 있습니다.

In computer science, a segment tree, also known as a statistic tree, is a tree data structure used for storing information about intervals, or segments. It allows querying which of the stored segments contain a given point.

A segment tree for a set I of n intervals uses O(n log n) storage and can be built in O(n log n) time. Segment trees support searching for all the intervals that contain a query point in time O(log n + k), k being the number of retrieved intervals or segments.

 

이걸 다음과 같이 정리해볼 수 있을 것 같습니다.

• 컴퓨터 과학에서 세그먼트 트리는 통계 트리라고도 불리며, 구간과 부분과 관련된 정보를 저장하기 위해 사용한다.
• 세그먼트 트리를 사용시 저장된 세그먼트 중 어떤 세그먼트에 지정된 지점이 포함되어 있는지를 확인할 수 있습니다.
• 세그먼트 트리는 n log n의 공간을 요구하며, 한 번 build 하기 위해 n log n의 시간이 소모된다.
• 세그먼트 트리가 한 번 만들어지면, 구간과 관련된 요구에 log (n + k)의 시간이 소모된다.
• k는 반환되는 구간 혹은 세그먼트(질의 결과)의 숫자를 의미한다.

 

요약을 나름 해보자면, 다음과 같습니다!👍🏼👍🏼`

세그먼트 트리는 O(nlogn)의 시간을 들여 O(nlogn)의 공간에 만들어지며, 한 번 세그먼트 트리를 만들면 구간에 대한 질의(구간 합, 구간의 최소 or 최댓값)에 log(n + k)의 시간이면 응답이 가능하다!! (k는 반환되는 구간 또는 세그먼트의 크기)

---

세그먼트 트리를 만드는 방법

세그먼트 트리를 이용해 다음의 두 가지 작업을 빠르게 수행할 수 있습니다.

1. 구간 합을 구하는 목적
2. 구간의 최댓값 또는 최솟값을 구하는 목적

우선 배열 하나가 있다고 가정하면, 이 배열에 대해 구간 질의를 하는 상황에 세그먼트 트리를 사용할 수 있을 것입니다.

 그러니까 일단 세그먼트 트리를 만들어야겠죠?

 

세그먼트 트리는 다음 방법을 따라가면 만들 수 있다고 합니다.

 

<일단 구간 합을 구하고 싶은 상황이라고 가정하고 구간 합에 대한 세그먼트 트리를 만들어 보겠습니다!>

 

1. 배열의 크기가 N일 때 NlogN 크기의 트리를 만든다.
2. 트리는 이진 트리 형태를 갖고, 트리의 루트에서 내려갈수록 좁은 구간에 대한 구간 합의 값을 저장한다.
3. 재귀적으로 트리의 값을 계산하며 트리를 채워준다.

그림으로 예를 들자면, 11개의 원소의 구간 합을 구하기 위한 세그먼트 트리를 만든다면

 

대략 위의 그림 같은 느낌으로 테이블이 생성되는 구조입니다. 세그먼트 트리의 리프(leaf)는 각 원소의 값을 갖게 될 것이고, 리프에서 올라가면서 양쪽 노드의 합이 저장되는 구조로 세그먼트 트리를 만들어 구간 합을 저장하도록 구현할 수 있습니다.

 

이런 식으로 세그먼트 트리가 만들어지기 때문에, 높이가 logN인 트리가 만들어지고, 트리의 사이즈가 NlogN이 요구되는 구조 이게 된 것입니다. (리프 노드의 수(N) x 트리의 높이(logN)이므로)

 

추가로 세그먼트 트리는 이진 트리의 형태로 만들어지므로, 왼쪽 child node는 현재 인덱스에 x2를 오른쪽 child node는 x2 + 1을 하면 접근할 수 있다는 장점 또한 가지고 있습니다.

 

이제 이러한 세그먼트 트리의 성질을 정리했으니, C++ 언어를 이용해서 구간합을 구하는 세그먼트 트리를 구현해 보도록 하겠습니다.

---

세그먼트 트리를 만들어보자 (C++로)

우선 가장 처음에 설명할 부분은 세그먼트 트리를 초기화하는 코드입니다.

해당 함수는 parameter로 start, end, node를 받는데, 각각의 인자가 의미하는 바는 다음과 같습니다.

1. start: 시작 index (원하는 구간의)

2. end: 끝 index (원하는 구간의)

3. node: 현재 segment tree의 index

 

코드를 간단히 설명하자면, 원하는 구간의 시작과 끝이 같은 경우에는 배열의 원소 하나를 뜻한다고 판단하여 세그먼트 트리의 해당 칸에 배열의 값을 그대로 할당하고 그 값을 반환합니다.

 

그렇지 않은 경우에는, mid값을 구해 구간을 반으로 나눠서 재귀적으로 init 함수를 호출해 왼쪽 구간의 합을 구하고 오른쪽 구간의 합을 각각 구해 현재 세그먼트 트리의 칸에 담는 구조로 동작합니다.

 

다음 부분은 세그먼트 트리를 이용해서 구간의 합을 구하는 함수를 구현한 코드입니다.

앞서 만들어낸 세그먼트 트리는 구간을 반으로 계속 쪼개면서 구간의 합을 저장하고 있는 구조이기 때문에, 우리가 원하는 모든 구간에 대한 구간 합을 구하려 하는 경우 추가적인 구현이 필요합니다.

이 함수는 start, end, node 등의 parameter를 이용해 세그먼트 트리의 현재 칸이 저장하고 있는 구간 합의 정보를 다음 함수의 호출에게 알려주는 역할을 수행합니다.

 

우리가 원하는 구간의 정보는 left, right index가 전달하는 느낌으로 이해하면 될 것 같습니다.

 

함수는 크게 현재 구간의 합 정보가 내가 원하는 구간에 포함되는 경우에는 현재 구간 합의 값을 반환하고, 포함되지 않는 경우 0을 반환하는 방식으로 동작합니다.

 

여기서 또 생각해야 하는 경우가 생기는데, 구간의 일부가 원하는 구간에 포함되고, 나머지는 그렇지 않은 경우일 때입니다. 이 경우에는 구간을 다시 반으로 쪼개서 포함 여부를 판단하기 위해서 재귀적으로 sum 함수를 호출하게 됩니다.

 

이때, 원하지 않는 구간인 경우 0을 반환하는 이유를 알게 되는데, 바로 원하지 않는 경우에는 그냥 더하면 안 되기 때문입니다. 코드를 직접 돌려보면 쉽게 알 수 있습니다.

 

또 저는 사실 알고리즘 문제 풀이에 세그먼트 트리를 주로 사용해서 트리를 갱신할 필요는 없었지만, 세그먼트 트리를 갱신하는 부분도 중요하여 이 부분도 정리하려 합니다.

트리를 갱신하는 부분의 코드입니다. 

 

세그먼트 트리에 저장된 값은 우리가 구간합을 구하길 원하는 원 배열(혹은 리스트)가 바뀌는 경우에도 갱신되어야 변경 이후에도 우리가 원하는 구간 연산을 가능하게 해 줍니다.

 

이 함수 또한 재귀적으로 실행되는데, 간단히 설명하자면 구간을 계속 쪼개면서 변경된 배열의 값을 포함하는 구간의 경우 차이 값(dif)을 구간 합에 반영하는 연산을 수행하게 됩니다. (값이 작게 바뀌었으면 dif가 -값을 갖겠죠?)

 

제가 구현한 전체 코드는 다음과 같습니다! (전체적인 코드의 구현은 안경잡이 개발자 블로그에서 많이 참고했습니다!!)

---

세그먼트 트리를 사용하는 이유에 대한 생각

 

세그먼트 트리의 정의를 살펴볼 때 확인했던 것과 같이 세그먼트 트리는 일반 리스트보다 많은 공간을 사용하는 대신에, 한 번 만들어진 경우 구간합 또는 구간의 최대 최솟값을 구하는 작업을 빠르게 수행할 수 있도록 합니다.

 

따라서 세그먼트 트리를 사용하게 되면, 사용하는 메모리와 시간의 trade-off가 발생하고 이로 인해서 공간을 더 점유하는 것보다는 시간을 단축시키고 싶은 경우 세그먼트 트리를 사용하는 것이 아닐까라는 생각이 들었습니다.