<java> 세그먼트 트리 segment tree

세그먼트 트리

여러 개의 데이터가 연속적으로 존재할 때 특정한 범위의 데이터의 합을 구하는 방법

특정 구간의 합을 가장 빠르게 구하는법

 

1. 기존방식

순서대로 하나씩 들고와서 더하기 → 시간복잡도 O(N)

 

2. 트리구조로 구하기

세그먼티 트리 초기화 및 생성 함수
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
tree = [0] * (len(arr) * 4)​

 

세그먼트 트리의 크기는 배열의 개수 N일 때,

N보다 큰 가장 가까운 N의 제곱수를 구해 그것의 2배를 하여 미리 크기 구하기

→  실제로는 데이터의 개수 N에 4를 곱한 크기만큼 미리 세그먼트 트리의 크기 할당

 

 

왼쪽 자식 노드의 번호는 2번이 되며, 0~4까지의 arr 구간 합의 값이 삽입된다.
오른쪽 자식 노드의 번호는 3번이 되며, 5~9까지의 arr 구간 합의 값이 삽입된다.

세그먼트 트리의 인덱스가 1번부터 시작하는 이유는 재귀적으로 편하게 세그먼트 트리를 생성하기 위해서이다. 1부터 시작하게 되면 2를 곱했을 때는 왼쪽 자식 노드를 가리키고, 2를 곱하고 1을 더하면 오른쪽 자식 노드를 가리키게 되어 효과적이기 때문이다.

# <세그먼트 트리를 배열의 각 구간 합으로 채워주기>
# start : 배열의 시작 인덱스, end : 배열의 마지막 인덱스
# index : 세그먼트 트리의 인덱스 (무조건 1부터 시작)
def init(start, end, index):
    # 가장 끝에 도달했으면 arr 삽입
    if start == end:
        tree[index] = arr[start]
        return tree[index]
    mid = (start + end) // 2
    # 좌측 노드와 우측 노드를 채워주면서 부모 노드의 값도 채워준다.
    tree[index] = init(start, mid, index * 2) + init(mid + 1, end, index * 2 + 1)
    return tree[index]

 

세그먼트 트리로 구간 합 구하는 함수

세그먼트 트리는 트리 구조이기 때문에 데이터를 탐색하는데 있어 O(logN)의 시간 복잡도를 가진다. 따라서 구간 합을 항상 O(logN)의 시간에 구할 수 있다.

 

구하고자 하는 6~9의 범위의 구간 합은 7 + 8 + 9 + 10 = 34이다. 전에 세그먼트 트리에서 인덱스 7의 원소값은 19, 인덱스 13의 원소값은 8, 인덱스 25의 원소값은 7이었다. 즉, 구하고자 하는 값은 7 + 8 + 19 = 34가 되는 것이다.