세그먼트 트리

♠ 세그먼트 트리

세그먼트 트리란? 특정 구간(segment)에 대한 구간 값을 트리에 저장한 자료 구조. 

 

nums = [1, 2, 3, 4, 5]

 

배열(리스트) 안의 숫자를 모두 더한다고 했을 때, 위의 숫자배열은 짧기 때문에 처음부터 끝까지 요소를 하나씩 가져오면서 더해도 되지만 배열 길이가 길어질수록 시간이 오래 걸리게 된다. 그래서 어느 정도 구간의 합은 미리 구해서 저장하고 필요할 때만 사용하는 방법으로 세그먼트 트리를 사용한다. 

 

세그먼트 트리는 이진트리를 기본으로 한다. 배열의 길이 n이 2의 제곱꼴인 경우, 완전이진트리가 되며 그때 트리의 높이는 logN이다. N이 2의 제곱꼴이 아닌 경우, 높이는 H=[logN]이다. 길이가 10인 배열을 세그먼트 트리로 나타내면 다음과 같다. 

 

그리고 각 노드의 번호는 아래와 같다. 

 

[노드 번호와 노드 값 대응]

노드 번호	노드 값	노드 번호	노드 값	노드 번호	노드 값	노드 번호	노드 값
1	idx 0~9의 합	6	idx 5~7의 합	11	idx 4의 값	16	idx 0의 값
2	idx 0~4의 합	7	idx 8~9의 합	12	idx 5~6의 값	17	idx 1의 값
3	idx 5~9의 합	8	idx 0~1의 합	13	idx 7의 값	24	idx 5의 값
4	idx 0~2의 합	9	idx 2의 값	14	idx 8의 값	25	idx 6의 값
5	idx 3~4의 합	10	idx 3의 값	15	idx 9의 값

 

 

 

♠ 세그먼트 트리 구현하기

Top-Down 방식(재귀적 방식)

 

tree = [0] * 2**(ceil(log(n, 2) + 1))

def segment(left, right, i=1):
    if left == right:
        tree[i] = nums[left]
        return tree[i]
 
    mid = (left + right) // 2
 
    tree[i] = segment(left, mid, i*2) + segment(mid+1, right, i*2+1)
    return tree[i]

• nums = 구간합을 구하고자 하는 입력 배열. n는 nums의 길이
• tree = 세그먼트 트리가 저장될 배열. 트리의 노드들이 차례대로 저장된다. 
• tree[i] = 트리에서 i번째 노드가 표현하는 구간 합
• tree[1] = 루트 노드로, 전체 구간을 표현
• 왼쪽 자식은 i * 2 로, 오른쪽 자식은 i * 2 +1 로 표현된다.
• segment(left, right, i)는 배열 nums의 [left, right] 구간을 처리하며 그 구간에 해당하는 값을 트리의 i번째 위치에 저장한다. 
• left == right 인 경우, 구간의 길이가 1이므로 nums[left]의 값을 트리의 i번째 위치에 저장하고 반환한다.  
• left != right 인 경우, [left, right]의 중간 지점인 mid를 구하고, 왼쪽 구간 [left, mid]와 [mid+1, right]에 대해 재귀적으로 트리를 구축한다. 
• 왼쪽 자식은 i * 2, 오른쪽 자식은 i * 2 + 1 에 저장된다.
• 왼쪽 자식 구간의 합과 오른쪽 자식 구간의 합을 더해서 i번째 노드에 저장한다.  

 

[배열과 세그먼트 트리 예시와 코드 구현] 

 

 

 

출력된 트리의 값

 

 

 

♠ 세그먼트 트리를 사용하는 이유

1. 효율성

세그먼트 트리의 가장 큰 장점은 구간에 대한 질문을 O(logN) 시간에 처리할 수 있다는 점이다. 이는 구간을 조개는 방식이 이진 트리 구조이기 때문에 가능하다. 트리의 높이는 logN이므로 구간의 합이나 최소/최대값 같은 연산을 빠르게 처리할 수 있다. 

 

2. 구간 갱신

트리 구간에 대해 값을 갱신할 때도 비슷한 시간 복잡도로 효율적인 처리가 가능하다. 

 

 

 

♠ 참고 자료

https://cheon2308.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%84%B8%EA%B7%B8%EB%A8%BC%ED%8A%B8-%ED%8A%B8%EB%A6%ACSegment-Tree

[Algorithm] 세그먼트 트리(Segment Tree) with Python

 

https://cheon2308.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%84%B8%EA%B7%B8%EB%A8%BC%ED%8A%B8-%ED%8A%B8%EB%A6%ACSegment-Tree

[Algorithm] 세그먼트 트리(Segment Tree) with Python