[세그먼트 트리] 구간합 구하기 / 원소 변경에서 시간복잡도를 줄이자!

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

세그먼트 트리 (Segment Tree)

 

자세한 글과 그림은

위 baekjoon의 창시자가 직접 쓴 글에 존재합니다.

 

배열 A가 있고, 여기서 다음과 같은 두 연산을 수행해야하는 문제를 생각해봅시다.

1. 구간 l, r (l ≤ r)이 주어졌을 때, A[l] + A[l+1] + ... + A[r-1] + A[r]을 구해서 출력하기
2. i번째 수를 v로 바꾸기. A[i] = v

수행해야하는 연산은 최대 M번입니다.

세그먼트 트리나 다른 방법을 사용하지 않고 문제를 푼다면, 1번 연산을 수행하는데 O(N), 2번 연산을 수행하는데 O(1)이 걸리게 됩니다. 총 시간 복잡도는 O(NM) + O(M) = O(NM)이 나오게 됩니다.

2번 연산이 없다고 생각해봅시다.

수를 바꾸는 경우가 없기 때문에, 합도 변하지 않습니다. 따라서, 앞에서부터 차례대로 합을 구해놓는 방식으로 문제를 풀 수 있습니다.

S[i] = A[1] + ... + A[i] 라고 했을 때, i~j까지 합은 S[j] - S[i-1]이 됩니다.

i~j까지 합은 A[i] + ... + A[j]인데, S[j] = A[1] + ... + A[j], S[i-1]= A[1] + ... + A[i-1] 이기 때문입니다.

S[0] = A[0];
for (int i=1; i<n; i++) {
    S[i] = S[i-1] + A[i];
}

여기서 2번 연산을 하려면, 수가 바뀔때마다 S를 변경해줘야 합니다. 가장 앞에 있는 0번째 수가 바뀐 경우에는 모든 S 배열을 변경해야 하기 때문에, 시간복잡도는 O(N)이 걸리게 됩니다.

따라서, M과 N이 매우 큰 경우에는 시간이 너무 오래걸리게됩니다.

 

세그먼트 트리

세그먼트 트리를 이용하면, 1번 연산을 O(lgN), 2번 연산도 O(lgN)만에 수행할 수 있습니다.

 

세그먼트 트리가 존재하는 이유입니다. 

위와 같은 두가지 연산에서 시간복잡도를 log로 떨어트릴 수 있는 것이죠.