세그먼트 트리

세그먼트 트리는 리스트에서의 부분합 계산을 할때 O(N)이 걸리는 것을 보완하기 위해서 설계된 알고리즘으로써 노드 기준 왼쪽은 왼쪽합 오른쪽은 오른쪽 합을 자식으로 두는 이진 트리 입니다.

10개의 원소를 가진 세그먼트 트리 구조힙니다.

알고리즘

일단 트리를 만들려면 적당한 길이의 리스트가 필요합니다. 리스트의 길이는 원소의 갯수보다 큰 2의 거듭제곱 수 중 가장 작은 수를 선택하면 된다. 즉 2 ^ log2(원소갯수) + 1로 설정해주면 된다.

h = int(math.log2(len(list))) + 1
tree = [0 for _ in range(2**h)]

def makeTree(node, start, end):
    if start == end:               ## 원소 하나 단위 합을 구할때 재귀를 빠져나오기 시작한다.
        tree[node] = list[start]
        return tree[node]
    tree[node] = makeTree(node * 2, start, (start + end) // 2 ) + makeTree(node * 2 + 1, (start + end) //2  + 1, end)
    return tree[node]

트리를 구성하는 알고리즘은 다음과 같고 재귀를 이용하여 구현할 수 있습니다.

그리고 트리를 구성했으면 트리를 이용해서 부분합을 구하는 알고리즘을 구현하여야 합니다.

def searchSum(start, end, index, left, right):
    if left > end or right < start:     ## 범위 밖에 있을때
        return 0
    if left <= start and right >= end:  ## 범위 안에 있을때
        return tree[index]
    ## 범위 밖 & 안에 있을때 
    return searchSum(start, (start + end) //2, index * 2, left, right) + searchSum((start + end) // 2 + 1, end, index * 2 + 1, left, right)