[SW 정글 15일차] 세그먼트 트리

오늘은 분할 정복 문제를 풀면서 다른 사람의 코드를 찾아보는 일이 많았다.

다른 사람들의 문제 풀이에 대한 설명에서는 세그멘트 트리라는 용어가 종종 보였고 이것에 대한 개념 자체가 없어서 오늘 공부한 것을 바탕으로 정리해보려고 한다.

 

 

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

세그먼트 트리는 데이터의 합을 가장 빠르고 간단하게 구할 수 있는 자료구조로 여러 개의 데이터가 연속적으로 존재할 때 특정한 범위의 데이터의 합을 구하고자 할 때 사용한다.

세그먼트 트리를 쓰지않고 특정한 범위의 데이터의 합을 구할 때는 선형적인 방법을 사용할 것이다.

선형적인 방법이라 함은 어떠한 배열이 있을 때 인덱스 i ~ j까지 요소의 합을 구하려면 해당 범위의 요소를 하나씩 더해나가는 것이다.

이렇게 되면 시간복잡도가 O(n)이 될 것이고 n이 커진다면 시간복잡도 면에서 그리 좋지는 않다.

 

이러한 문제점을 해결하기 위해 트리 구조를 이용하는 것이다.

트리 구조의 특성상 합을 구할 때 시간 복잡도 O(log n)이면 된다.

길이가 10인 배열의 구간별 합을 구한다고 했을 때 사용하는 세그먼트 트리가 아래의 그림과 같다.

세그먼트 트리에 대해 간단히 설명하면 리프 노드는 배열의 수 그 자체를 의미한다.

리프 노드 이외의 노드는 왼쪽 자식과 오른쪽 자식의 합을 저장한다.

여기서, 노드 위에 표시한 숫자들은 인덱스 번호를 의미한다.

기본 트리와 다른 점은 루트 노드가 0이 아닌 1이라는 것이다.

그 이유는 어떠한 노드의 인덱스 번호 X에서 2를 곱하면 왼쪽 노드, 2를 곱하고 1을 더하면 오른쪽 노드를 가리키게 하기 위해서이다.

 

세그먼트 트리는 아래의 코드를 통해 만들 수 있다.

# a: 배열
# tree: 세그먼트 트리
# node: 세그먼트 트리 노드 번호

def segment_tree(start, end, node):
    if start == end:
        return tree[node] = a[start]
    
    mid = (start + end) / 2
    
    else:
    return tree[node] = init(start, mid, mode * 2) + init(mid + 1, end, node * 2 + 1)

start == end인 경우는 node가 리프 노드인 경우이므로 해당 노드에 a[start]값만 대입한다.

위에서 얘기한대로 어떠한 node의 왼쪽 자식은 node*2, 오른쪽 자식은 node*2+1이 된다.

그리고

node가 담당하는 구간이 [start, end]라면 왼쪽 자식은 [start, (start+end)/2], 오른쪽 자식은 [(start+end)/2+1, end]를 담당한다.

그러므로 재귀 함수를 이용해서 왼쪽 자식과 오른쪽 자식 트리를 만들고 그 합을 저장하는 것이다.

 

 

 

2. 세그먼트 트리에서 합 구하기

그러면 이제 가장 중요한 세그먼트 트리의 기능인 특정 구간의 합을 얻는 과정이다.

구간 [left, right]가 주어졌을 때 해당하는 구간의 합을 찾으려면 루트부터 트리를 순회하면서 각 노드가 담당하는 구간과 찾고자하는 구간사이의 관계를 살펴봐야 한다.

 

예를 들어 5 ~ 8번까지의 합을 구하고자 한다.

그러면 트리 탐색 후 아래의 그림에 표시한 것처럼 6번 인덱스와 14번 인덱스를 참조하여 답을 얻을 수 있다.

어떠한 node가 담당하고 있는 구간이 [start, end]이고 합을 구해야하는 구간이 [left, right]라면 트리를 탐색하면서 4가지 경우가 발생한다.

1. [left, right]와 [start, end]가 아예 겹치지 않는 경우 (ex. [left, right] = [1, 3], [start, end] = [4, 6])

2. [left, right]가 [start, end]를 완전히 포함하는 경우 (ex. [left, right] = [1, 6], [start, end] = [2, 5])

3. [start, end]가 [left, right]를 완전히 포함하는 경우 (ex. [left, right] = [2, 5], [start, end] = [1, 6])

4. [left,right]와 [start,end]가 겹쳐져 있는 경우 (1, 2, 3 제외한 나머지 경우) (ex. [left, right] = [1, 4], [start, end] = [2, 7])

 

위 경우의 수들을 코드로 구현하면 아래와 같다.

def sum(node, start, end, left, right):
    # 아예 겹치지 않는 node이므로 pass (1번 경우의 수)
    if left > end or right < start:
        return 0
    
    # 해당 노드가 찾고자 하는 구간을 포함하고 있으므로 그 노드를 반환(2번 경우의 수)
    if left <= start and right >= end:
        return tree[node]
    
    return sum(node * 2, start, (start + end) // 2, left, right) + sum(node * 2 + 1, (start + end) // 2 + 1, end, left, right)

 

 

 

3. 세그먼트 트리 수정하기

기존의 배열에서 어떠한 인덱스의 요소가 변경되었다면 해당하는 인덱스를 포함하는 구간을 가지고 있는 모든 노드를 변경시켜줘야한다.

예를 들어, 배열의 3번째 인덱스 요소가 변경되었다면 세그먼트 트리에서는 아래의 그림에 표시된 노드를 변경시켜야 한다.

그러면 수정된 값을 어떻게 노드에 반영을 할까?

먼저, 배열의 어떠한 인덱스의 요소 값이 b(원래값)에서 a(변경값)로 변경되었다면 a(변경값) - b(원래값)로 두 값의 차를 구한다.

아래에서부터는 두 값의 차를 diff라고 하겠다.

그러면 이제 세그먼트 트리를 순회하면서 어느 노드를 변경시켜야할지 판단해야하는데 여기서 2가지 경우가 나온다.

1. 노드의 구간 [start, end]에 인덱스가 포함되는 경우

1. 노드의 구간 [start, end]에 인덱스가 포함되지 않는 경우

 

해당 경우의 수를 구현한 코드는 아래와 같다.

def update(node, start, end, index, diff):
    if index < start or index > end:
        return
    
    tree[node] += diff
    
    if start != end:
        update(node * 2, start, (start + end) // 2, index, diff)
        update(node * (2 + 1), (start + end) // 2 + 1, end, index, diff)

코드는 index가 노드의 범위 밖에 있으면 탐색을 중단하고 범위 안에 있다면 diff를 더해준다.

diff를 더해준 후에도 해당 노드가 리프노드가 아니라면 재귀로 탐색을 더 진행해준다.

 

---

[오늘의 나는 어땠을까?]

오늘은 왠지 모르게 너무 피곤했던 하루였다.

전 날에도 피로감이 너무 쌓여있어서 조금 잠을 더 자고자 1시에 기숙사에 들어갔다.

룸메 형과 이런저런 얘기를 하면서 취침시간은 조금 늦어졌지만 어느정도 잠은 충분히 잤다고 생각했다.

하지만 오늘 아침부터 굉장히 피곤했고 점심을 먹은 뒤 40분 정도 낮잠을 잤지만 그래도 피곤해서 기숙사에서 1시간동안 푹 자고 나왔다.

다행히 피로감은 회복되어 그 이후로 공부를 제대로 할 수 있었다.

 

나는 개인적으로 잠은 5시간에서 5시간 30분이면 충분하다고 생각한다.

(물론, 정글에 들어오기 전에는 잠이라는 것을 너무 좋아해서 10시간 정도는 잔 것같다.)

더 자고 싶은 욕구는 항상 있지만 나에게는 10분, 20분이라는 시간은 너무 소중하고 시간은 만들 수 없으므로 내게 지금 주어지는 시간을 잘 활용해야한다.

하지만, 오늘같이 피로감에 쌓여 깨어있는 시간을 효율적으로 사용하지 못한다면 잠을 더 자는게 낫겠다는 생각을 하기도 했다.

어는 방법이 더 효율적인지 아직은 판단을 할 수 없지만 일단은 취침시간은 유지하고 너무 피곤하면 낮잠을 푹 자고 오는 방법을 선택할려고 한다.

 

지금 나의 최대의 적은 잠, 피곤함, 피로다.

 

---

<참고 자료>

https://m.blog.naver.com/ndb796/221282210534

https://www.acmicpc.net/blog/view/9