[PS를 위한 자료구조 1강] 세그먼트 트리의 원리와 시간복잡도

 

PS를 위한 컴퓨터 자료구조 강의 1강

 

# 세그먼트 트리의 원리와 시간복잡도 # 에 대해 알아보겠습니다.

강의에 들어가기에 앞서 모든 의사 코드는 파이썬의 문법을 모방하여 전해드리겠습니다.

 

 

[구간 합 구하기 4]

https://www.acmicpc.net/problem/11659

 

[구간 합 구하기 5]

https://www.acmicpc.net/problem/11660

 

혹시나 위의 문제를 해결하지 못하신 분들을 위해 해설해드리면 위 문제의 지문을 곧이 곧대로 구현하면 TLE(Time Limit Error)를 받게 됩니다.

 

ex) for (Q번 반복) :
	i, j = 인풋()
	print(sum(A[i:j]))

 

이 경우, 한 번의 쿼리당 최대 100000번의 연산이 발생하므로,

발생할 수 있는 최대 연산의 수는 O(N^2)으로 대략 100억번의 연산을 수행해야합니다.

파이썬은 대략 1초에 1억번의 연산을 아슬아슬하게 수행하므로 대략 100초의 시간이 걸릴 수 있음을 알 수 있죠.

 

 

그렇다면 어떻게 해야할까요?

바로 누적합 (prefix sum)을 이용하는 겁니다. 미리 더해놓은 것을 이용하자는 겁니다.

 

S[i] = sum(A[1.. i]) (1부터 i의 합)

로 정의합시다.

(인덱싱은 파이썬과 다르게 편의상 i도 포함하겠습니다.)

 

그렇다면 S[i, j]를 구해봅시다.

 

S[j] = A[1] + A[2] + ... + A[i-1] + A[i] + ... + A[j-1] + A[j]
S[i-1] = A[1] + A[2] + ... + A[i-1]

이렇게 S[j] 와 S[i-1]를 구할 수 있습니다.

여기서 차이를 구해주면 다음과 같이 됨을 알 수 있습니다.

S[1, j] - S[1, i-1] = S[i, j] = A[i] + .... + A[j]

이것이 각 쿼리의 답이 되는 것이죠. 그림으로 보면 다음과 같습니다.

 

 

만약 S[i]를 모두 전처리를 통해 알고 있다면, 단 한번의 뺄셈으로 답을 구할 수 있는 것이죠.

즉, 한 번의 쿼리당 O(1)의 시간으로, 총 O(N)의 시간복잡도로 문제를 해결할 수 있습니다.

 

구간 합 구하기 5 역시 이를 응용해서 해결할 수 있습니다.

 

S[x , y]를 [1,1] 를 왼쪽 위 꼭짓점, [x,y]를 오른쪽 아래 꼭짓점으로 하는 정사각형의 누적합으로 정의하면,

포함 배제의 원리로 간단하게 해결할 수 있습니다.

 

 

이제부터 세그먼트 트리의 유용함에 대해 설파해보겠습니다.

아래의 문제를 읽고 오세요.

 

[구간 합 구하기]

https://www.acmicpc.net/problem/2042

 

위 문제들과의 차이점이 뭘까요?

혹시 발견하셨나요?

 

바로 '업데이트'가 있다는 것입니다.

 

중간의 있는 수들이 바뀌는 것이죠.

구간 합 구하기 4의 방식으로는 해결할 수 없는데, 하나의 숫자를 바꾸면

그 뒤쪽의 모든 누적합이 바뀌어야하기 때문이죠.

업데이트 쿼리 하나당 O(N)의 시간이 소요되어 TLE를 받게 됩니다.

 

 

세그먼트 트리는 이 업데이트 연산을 수행하기 위해, 구간을 쪼개어 구간마다 누적합을 구해놓습니다..!

구조를 눈으로 보며 설명하겠습니다.

 

다음의 그림을 봅시다.

8개의 원소가 있는 A를 다음과 같이 쪼개어 각각의 칸에 누적합을 구해놓았다고 가정합니다.

 

각 칸의 맨 왼쪽은 구간의 시작점, 맨 오른쪽은 구간의 끝점을 나타내는 것으로

[1 4]라고 하면 A[1] + A[2] + A[3] + A[4] 가 더해져 있는 것입니다.

 

한 계층마다 구간을 절반으로 쪼개어 더하는 것을 관찰하실 수 있을 것이며, 이것이 세그먼트 트리의 핵심입니다..

예시를 들어 다음과 같은 A가 있다고 해볼게요.

 

A = [ 1, 2, 3, 4, 5, 6, 7, 8 ]

그리고 이 배열로 위 그림을 완성해보겠습니다.

각 구간의 합을 위와 같이 구할 수 있을 겁니다.

만약 여기서 A[3] 에 4를 더하는 업데이트가 들어왔다고 하겠습니다.

이 때 바뀌어야하는 값은 A[3]이 포함되어 있는 구간만 바뀌면 될겁니다. 

다음의 그림을 보면 이해가 쉬울 겁니다.

3이 포함되어 있는 구간만 업데이트가 되는 걸 볼 수 있죠.

자, 그러면 중요한 업데이트 연산의 횟수를 봅시다..!

몇 번의 업데이트가 발생하나요? (4번!!)

 

맞습니다. 4번입니다.

각 계층마다 1번씩 업데이트가 일어나는 것을 확인할 수 있죠.

 

그러면 이 계층은 몇 개가 생기는 걸까요?

구간이 아래 계층으로 내려갈수록 매번 절반씩 쪼개어지므로 대략 logN개의 계층이 생길 것이라고 예상할 수 있습니다.

( 원소 8개 -> 4계층, 원소 16개 -> 5계층 )

 

각 계층마다 대략 logN번의 업데이트 연산이 일어남을 알 수 있습니다..!!

대략 배열의 크기가 1000000(백만) 이어도 대략 20번의 연산밖에 일어나지 않습니다. 

시간차이가 많이 날 수 밖에 없겠죠.

 

자, 그런데 아직 중요한 내용을 다루지 않았죠.

그래 업데이트 연산은 알겠어. 근데 구간의 합은 어떻게 구해?

 

구간의 합 쿼리를 수행하는 방법에 대해 설명하겠습니다.

이해를 돕기 위해 2부터 7까지의 구간합을 어떻게 구할 수 있는지 그림을 보죠.

위의 그림의 색칠된 부분을 모두 더하면 A[2] 부터 A[7] 까지의 모든 원소가 들어 있음을 확인할 수 있습니다. 

2부터 8까지의 예시를 하나만 더 볼게요.

역시 A[2]부터 A[8]까지 모든 원소가 합해져 있음을 알 수 있습니다.

 

특징은 쿼리 구간에 완전히 포함되는 구간 중 가장 큰 구간을 선택하는 것을 볼 수 있죠.

예를 들어 A[5]부터 A[8]까지의 합을 5-6 구간 + 7-8 구간으로 구하지 않습니다. 가장 적은 수의 연산을 하기 위해서죠.

 

이 연산 역시 logN번의 연산으로 구할 수 있습니다. 

이 부분은 '구현'파트에서 더욱 자세히 다뤄보겠습니다.

 

 

질문은 댓글도 좋고, 제 유튜브 채널에 오셔도 좋고, 아래의 오픈채팅방을 이용하셔도 좋습니다. 감사합니다.

그 외에 피드백은 자유롭게 작성해주세요..!

 

[유튜브 : 승욱은] 승욱은 - YouTube

[ 1:1 오픈채팅방] 카카오톡 오픈채팅 (kakao.com)