[Algorithm] 세그먼트 트리(Segment Tree) 알고리즘 이해하기

출처: https://www.geeksforgeeks.org/euler-tour-subtree-sum-using-segment-tree/

세그먼트 트리(Segment Tree) 알고리즘 이해하기

프로그래밍을 하다 보면, 종종 배열의 특정 구간에 대한 정보를 빠르게 처리해야 할 때가 있습니다. 예를 들어, 배열의 특정 구간에 대한 합계를 구하거나, 최소값 또는 최대값을 빠르게 찾아야 하는 경우입니다. 이런 문제를 단순한 방법으로 해결하려면 많은 시간이 걸릴 수 있지만, 이를 더 효율적으로 처리할 수 있는 자료 구조가 바로 세그먼트 트리(Segment Tree)입니다.

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

세그먼트 트리는 배열의 구간 정보를 트리 형태로 저장하는 자료 구조입니다. 이를 사용하면 배열의 특정 범위에 대한 질의(query)를 매우 빠르게 처리할 수 있습니다. 예를 들어, 구간의 합을 구하는 문제를 생각해볼 수 있습니다. 단순한 방법으로는 배열의 요소를 처음부터 끝까지 모두 더해야 하지만, 세그먼트 트리를 사용하면 원하는 구간에 해당하는 부분만 빠르게 조회할 수 있습니다.

세그먼트 트리는 각 구간의 정보를 이진 트리 형태로 저장합니다. 배열을 절반씩 나누어 트리의 각 노드에 구간의 정보를 저장하고, 리프 노드는 배열의 개별 요소를 나타냅니다. 이렇게 트리를 구성하면 구간의 정보를 O(log⁡ N)의 시간 복잡도로 처리할 수 있어 매우 효율적입니다.

세그먼트 트리(Segment Tree)의 기본 연산

세그먼트 트리는 주로 두 가지 중요한 연산을 지원합니다: 구간 질의와 구간 업데이트입니다.

트리 생성 (Build)

먼저 세그먼트 트리를 생성하는 과정부터 살펴보겠습니다. 배열을 기반으로 트리를 구성하며, 각 노드는 배열의 특정 구간에 대한 정보를 저장합니다. 트리의 크기는 배열의 크기보다 약 네 배 정도 큰데, 이는 모든 구간을 저장할 공간을 확보하기 위해서입니다.

def query(self, l, r):
    l += self.n
    r += self.n
    result = 0
    while l <= r:
        if l % 2 == 1:
            result += self.tree[l]
            l += 1
        if r % 2 == 0:
            result += self.tree[r]
            r -= 1
        l //= 2
        r //= 2
    return result

위 코드는 세그먼트 트리를 구성하는 간단한 파이썬 코드입니다. 트리를 생성하는 과정은 배열의 데이터를 트리의 리프 노드에 먼저 배치하고, 그 위의 부모 노드들은 자식 노드의 합계를 계산하여 채워넣는 방식으로 진행됩니다. 이 과정은 O(n)의 시간 복잡도를 가집니다.

구간 질의 (Range Query)

트리가 생성되면, 이제 구간에 대한 질의를 처리할 수 있습니다. 예를 들어, 배열의 특정 구간의 합을 구하는 문제를 세그먼트 트리로 빠르게 해결할 수 있습니다.

def update(self, pos, value):
    pos += self.n
    self.tree[pos] = value
    while pos > 1:
        pos //= 2
        self.tree[pos] = self.tree[2 * pos] + self.tree[2 * pos + 1]

위 코드에서 query 함수는 배열의 구간 [l, r]에 대한 합계를 구하는 함수입니다. 트리의 리프 노드에서 시작해 상위 노드로 이동하며, 필요한 구간에 대한 정보를 빠르게 추출해 합계를 계산합니다. 이 과정은 O(log N)의 시간 복잡도를 가지며, 배열의 크기가 커질수록 매우 효율적입니다.

구간 업데이트 (Update)

구간의 값을 변경할 때도 세그먼트 트리는 효율적으로 동작합니다. 특정 값이 변경되면, 그 값이 포함된 구간에 대한 정보도 갱신해야 하기 때문에 트리의 해당 부분을 재계산해야 합니다.

def update(self, pos, value):
    pos += self.n
    self.tree[pos] = value
    while pos > 1:
        pos //= 2
        self.tree[pos] = self.tree[2 * pos] + self.tree[2 * pos + 1]

위 코드에서는 배열의 특정 위치의 값을 변경하고, 그 값을 기반으로 트리의 상위 노드들을 갱신하는 과정을 보여줍니다. 업데이트 작업도 마찬가지로 O(log⁡ N)의 시간 복잡도를 가집니다.

세그먼트 트리의 장단점

장점:

1. 구간 질의와 업데이트를 매우 빠르게 처리할 수 있습니다. 특히, 배열의 크기가 커질수록 그 효율성이 더욱 두드러집니다.
2. 배열에 대한 정보를 동적으로 관리할 수 있어, 다양한 문제에 응용할 수 있습니다. 구간 합뿐만 아니라, 최소값, 최대값을 구하는 문제 등에도 사용할 수 있습니다.

단점:

1. 트리 구조 자체가 복잡할 수 있어 처음 구현할 때 다소 난이도가 있습니다.
2. 배열의 크기가 작은 경우에는 이 자료 구조를 사용하는 것이 오히려 비효율적일 수 있습니다.

세그먼트 트리의 활용 예시: 구간 합 구하기

세그먼트 트리는 다양한 문제에서 효율적으로 사용될 수 있으며, 특히 구간 질의나 구간 업데이트와 같은 문제를 해결할 때 유용합니다. 아래는 구간 합을 구하는 예시를 통해 세그먼트 트리의 실전 적용 사례를 설명하고, 이를 구현하는 코드를 포함하여 상세히 설명하겠습니다.

1. 트리 생성 (Build)

먼저 배열을 기반으로 세그먼트 트리를 생성해야 합니다. 트리의 각 노드는 배열의 특정 구간에 대한 합을 저장합니다. 트리를 생성하는 함수는 배열을 재귀적으로 반씩 나누어 리프 노드(leaf node)에 배열의 각 요소를 저장하고, 부모 노드에 자식 노드의 합계를 저장합니다.

def build_segment_tree(arr, tree, node, start, end):
    if start == end:
        # 리프 노드에 배열 값 저장
        tree[node] = arr[start]
    else:
        # 배열을 반으로 나누고 좌우 서브 트리 생성
        mid = (start + end) // 2
        build_segment_tree(arr, tree, 2 * node + 1, start, mid)
        build_segment_tree(arr, tree, 2 * node + 2, mid + 1, end)
        # 좌우 서브 트리의 합을 부모 노드에 저장
        tree[node] = tree[2 * node + 1] + tree[2 * node + 2]

이 함수는 재귀적으로 배열을 나누어 세그먼트 트리를 구축하며, 배열의 크기가 n일 때 트리의 노드 개수는 대략 4n입니다.

2. 구간 질의 (Query)

구간의 합을 구하는 과정은 트리의 노드를 탐색하여 해당 구간에 속하는 노드들만을 더하는 방식으로 이루어집니다. 구간이 완전히 포함되는 경우에는 바로 그 노드의 값을 사용하고, 구간이 겹치는 경우에는 왼쪽과 오른쪽 서브트리를 각각 탐색해 결과를 합산합니다.

def query_segment_tree(tree, node, start, end, l, r):
    # 구간이 겹치지 않으면 0을 반환
    if l > end or r < start:
        return 0
    # 구간이 완전히 포함되면 해당 노드의 값을 반환
    if l <= start and r >= end:
        return tree[node]
    # 구간이 부분적으로 겹치면 좌우 서브 트리를 탐색
    mid = (start + end) // 2
    left_sum = query_segment_tree(tree, 2 * node + 1, start, mid, l, r)
    right_sum = query_segment_tree(tree, 2 * node + 2, mid + 1, end, l, r)
    return left_sum + right_sum

이 함수는 O(log⁡ N)의 시간 복잡도로 동작하며, 구간 질의가 효율적으로 처리됩니다.

3. 코드 실행 예시

다음은 세그먼트 트리를 구성하고, 구간 [1, 3]에 대한 합을 구하는 예시입니다.

arr = [1, 2, 3, 4, 5]  # 배열
n = len(arr)  # 배열 크기
tree = [0] * (4 * n)  # 세그먼트 트리 공간 할당

# 세그먼트 트리 생성
build_segment_tree(arr, tree, 0, 0, n - 1)

# 구간 [1, 3]의 합을 질의
result = query_segment_tree(tree, 0, 0, n - 1, 1, 3)
print(result)  # 출력: 9 (2 + 3 + 4)

이 코드는 배열 [1, 2, 3, 4, 5]에 대해 세그먼트 트리를 구성하고, 배열의 인덱스 1에서 3까지의 합을 구합니다. 결과적으로, 값 9가 출력됩니다.

세그먼트 트리의 실전 적용 사례

세그먼트 트리는 구간에 대한 질의와 업데이트를 빠르게 처리해야 하는 다양한 문제에서 응용될 수 있습니다. 예를 들어, 온라인 게임의 실시간 순위 갱신이나 자원 관리 시스템에서 효율적으로 활용됩니다. 이러한 응용에서는 특정 구간에서 리소스가 어떻게 사용되고 있는지, 혹은 실시간으로 데이터를 갱신하고자 할 때 세그먼트 트리를 사용하여 빠르고 정확하게 처리할 수 있습니다.

결론

세그먼트 트리는 구간 정보를 효율적으로 처리하기 위한 강력한 도구입니다. 구간 합, 최소값, 최대값 등 다양한 문제에서 뛰어난 성능을 발휘하며, 특히 대규모 데이터셋에서 그 진가를 발휘합니다. 처음 접할 때는 트리 구조와 재귀적인 구현이 다소 어렵게 느껴질 수 있지만, 기초적인 개념을 하나씩 이해하고 나면 이를 다양한 문제에 응용할 수 있는 폭이 넓어집니다.

세그먼트 트리는 실생활에서 사용하는 응용 프로그램의 성능을 향상시키는 중요한 자료 구조 중 하나입니다. 특히 실시간 데이터 처리나 대규모 시스템의 효율적인 리소스 관리 등 다양한 영역에서 널리 활용되고 있습니다. 따라서, 이러한 자료 구조를 이해하고 활용하는 것은 개발자로서의 성장에 큰 도움이 될 것입니다.