1. 세그먼트 트리
영어 단어 segment는 분할, 구간, 분절 등의 뜻을 지니고 있습니다.
알고리즘에서 세그먼트 트리는 여러 값을 가지는 리스트의 특정 구간의 정보를 이진 트리 형태로 관리하는 자료구조를 말합니다.
2. 세그먼트 트리가 만들어지는 과정
예를 들어, 1 ~ 10까지 10개의 숫자(원소)의 합을 세그먼트 트리로 만들면 다음과 같습니다.
가장 먼저 루트는 전체 범위의 정보를 가집니다.
그 정보가 숫자들의 합이므로 1~10까지의 합이 됩니다.
다만, 아직 그 정보의 값은 정해지지 않습니다.
왜냐하면 재귀적으로 자식을 만들고, 리프가 완성되었을 때 반환값을 통해 값이 정해지기 때문입니다.
이제 루트의 자식을 만듭니다.
이진 트리이므로 자식은 둘이며 범위는 반으로 나누어 줍니다.
그럼 자식은 각각 1~5, 6~10의 범위를 가집니다.
각각의 자식은 또 자신의 범위를 반으로 나눠 자식에게 나누어 줍니다.
더 이상 범위를 나눌 수 없을 때(원소가 될 때)까지 자식을 만들어나갑니다.
리프에 해당하는 노드들은 나눌 수 없는 범위의 값(원소의 값)을 가집니다.
리프가 완성되면, 원소의 값이 반환되어 다시 재귀적으로 부모 노드까지 올라갑니다.
루트까지 도달하면 전체 범위(1~10)의 합을 반환하고 세그먼트 트리가 완성됩니다.
3. 이진 트리의 구현
위에서 본 것처럼 세그먼트 트리를 만들기 위해서는 이진 트리를 구현해야 합니다.
이진 트리를 위한 특별한 자료형을 만들 수도 있겠으나, 배열(파이썬은 리스트)로 간단하게 이진 트리를 구현할 수 있습니다.
먼저, 루트 노드는 index 1에 할당합니다.
배열의 첫 번째 index인 0이 아님에 유의합니다.(index 0의 자리는 사용하지 않습니다.)
이제 부모 노드의 index 값을 i라고 하면 두 자식 노드는 index 값이 2i와 2i+1에 할당합니다.
이를 재귀적으로 반복하면 배열에 빈 자리가 없이, 그리고 겹치는 자리 없이 이진 트리의 모든 노드들을 할당할 수 있습니다.
이 방법은 이진 트리를 사용하는 힙 자료구조를 구현할 때에도 똑같이 사용됩니다.
배열의 길이는 어떻게 정해질까요?
이진 트리이기 때문에 자식으로 한 계단 내려갈 때마다 노드의 개수가 2배로 늘어납니다.
위의 예시에서 1 ~ 10까지 원소가 10개이므로, 이진 트리가 5층으로 만들어지고, 5층의 이진 트리는 2의 5승(32) 만큼의 자리가 필요함을 알 수 있습니다.
식으로 쓰면
\(2^{\left \lceil \log_{2}n \right \rceil + 1}\)
이지만, 계산이 귀찮고 위 값은 n에 4를 곱한 수보다 항상 작으므로 배열의 길이는 편하게 원소의 개수에 4를 곱해서 잡아도 무방합니다.
4. 세그먼트 트리에서 특정 범위의 값을 구하는 과정
세그먼트 트리의 각 노드는 일정한 범위와 그 범위에 해당하는 값을 가집니다.
따라서 우리가 알고자 하는 범위가 있으면, 그 범위에 포함되는 노드들을 재귀적으로 찾아 해당되는 값들을 통해 최종적으로 우리가 원하는 범위의 값을 구할 수 있습니다.
예를 들어 위에서 만든 세그먼트 트리에서 3 ~ 7의 범위의 값들의 합을 알고 싶다고 해봅시다.
먼저 루트는 1 ~ 10의 범위를 가지므로 우리가 원하는 범위를 벗어납니다.
따라서 자식들을 탐색합니다.
자식은 반의 범위인 1 ~ 5와 6 ~ 10의 범위를 가지므로, 역시 우리가 원하는 3 ~ 7의 범위에 포함되지 않습니다.
따라서 또 자식에게 넘어갑니다.
이제 범위가 점점 작아지면서 다음과 같은 경우가 발생할 수 있습니다.
바로 우리가 원하는 범위와 아예 겹치지 않는 노드이거나, 우리가 원하는 범위에 포함되는 노드입니다.
두 경우 모두 더 이상 탐색을 하지 않아도 되는 경우이며, 아예 겹치지 않는 노드는 결과에 영향을 미치지 않는 값을 반환시킵니다.(예시는 구간합이므로 0을 반환)
우리가 원하는 범위에 포함되는 노드는 자신이 가지고 있는 값을 반환합니다.
이제 탐색이 종료되면서 반환되는 값이 재귀적으로 올라갑니다.
이런 값들을 후처리(예시에서는 합)를 해서 최종값을 반환합니다.
우리가 원하는 3 ~ 7 구간의 합은 25라는 것을 알 수 있습니다.
5. 세그먼트 트리에서 특정 원소의 값을 수정하는 과정
세그먼트 트리의 장점은 특정 원소의 값을 수정하기가 용이하다는 점입니다.
그 이유는 루트에서 특정 원소(리프 노드)의 경로에 있는 노드의 값만 수정해주면 되기 때문입니다.
따라서 루트에서 특정 원소를 찾아가면서(내려가면서) 값을 수정하는 방법이 있고, 특정 원소를 찾은 뒤에 재귀적으로 다시 값을 반환하며 반환된 값을 사용하여 루트로 거슬로 올라가면서 값을 수정하는 방법이 있습니다.
먼저 내려가면서 값을 수정하는 경우에는 특정 원소의 값과 무관하게 노드들의 값을 수정해주어야 합니다.
그러기 위해서는 수정을 원하는 원소의 변화량이 필요합니다.
원소의 변화량 만큼 그 조상 노드들의 값이 변하기 때문에 변화량을 알고 있으면 내려가면서 노드들의 값을 수정할 수 있습니다.
예를 들어 위 세그먼트 트리에서 5번 원소의 값을 5에서 10으로 수정한다고 해봅시다.
그럼 변화량은 5이므로, 5번 원소를 찾아 내려가며 각 노드들의 값에 5만큼씩 더해주면 됩니다.
다음으로 수정할 원소에서 루트로 거슬러 올라가면서 값을 수정하는 방법이 있습니다.
이 때는 값을 수정하고 후처리도 할 수 있습니다.
내려가면서 수정할 때와는 달리 수정하지 않는 자식 노드의 값을 함께 사용하여 부모 노드의 값을 다시 계산하는 방식입니다.
마찬가지로 5번 원소의 값을 10으로 수정하게 되면, 수정할 노드에서 올라가면서 그림과 같이 조상 노드들의 값이 수정 됩니다.
