[2042] 구간 합 구하기

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

2042번: 구간 합 구하기

세그먼트 트리 기본문제다. 

 

풀이

세그먼트 트리란 구간합을 이진트리의 형태로 구현한 자료구조이다. 부모노드에는 두 자식노드의 총합이 담기며, 두 자식노드는 중간을 기준으로 좌측 범위의 총합, 우측 범위의 총합의 형태로 나뉜다. 그림으로 보는 것이 이해하기 더 쉬울 것이다.

크기 5인 배열의 세그먼트 트리의 구조다. 각 배열의 값이 리프노드에 담기며, 부모 노드로 구간 합을 계산하여 루트에는 배열의 총합이 담기게 된다.

 

예제 [1,2,3,4,5] 배열의 세그먼트 트리를 그려보면 다음과 같이 만들어진다. 세그먼트 트리의 경우 구간합의 변경에 굉장히 용이하다. 그 이유는 바로 트리구조에서 오는 접근성 때문인데, 부모 노드를 기준으로 두 배를 하면 좌측 자식 노드, 거기에 1을 더하면 우측 자식 노드에 접근이 가능하기 때문이다. 따라서 루트 노드는 0이 아닌 1부터 시작하며 기본적으로 해당 구조의 재귀호출을 통해 구간합의 변경과 조회가 이루어진다.

 

1번 ~ 4번 인덱스까지의 구간합을 구하게 된다면 좌측 그림과 같이 해당 구간에 접근하여 계산이 이루어진다. 사실 누적합을 이용해서 푼다면 O(1)만에 계산이 가능하지만, 자료의 변경이 일어난다면 처음부터 누적합을 다시 구해야 하기에, 결국 자료의 크기가 N일 때 O(N)시간이 걸리게 된다. 세그먼트 트리의 경우 우측 그림과 같이 조회뿐만 아니라 루트에서 해당 구간 만의 접근을 통해 변경이 가능하기에 O(logN)시간만에 해결이 가능하게 된다. 해당 문제의 경우 구간의 변경이 빈번하게 이루어지기에 세그먼트 트리의 구현을 요구하는 문제인 것이다.

 

정답 코드