[BOJ] 백준 2042번 : 구간 합 구하기 (JAVA)

문제

어떤 N개의 수가 주어져 있다. 그런데 중간에 수의 변경이 빈번히 일어나고 그 중간에 어떤 부분의 합을 구하려 한다. 만약에 1,2,3,4,5 라는 수가 있고, 3번째 수를 6으로 바꾸고 2번째부터 5번째까지 합을 구하라고 한다면 17을 출력하면 되는 것이다. 그리고 그 상태에서 다섯 번째 수를 2로 바꾸고 3번째부터 5번째까지 합을 구하라고 한다면 12가 될 것이다.

 

 

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄까지 N개의 수가 주어진다. 그리고 N+2번째 줄부터 N+M+K+1번째 줄까지 세 개의 정수 a, b, c가 주어지는데, a가 1인 경우 b번째 수를 c로 바꾸고 a가 2인 경우에는 b번째 수부터 c번째 수까지의 합을 구하여 출력하면 된다.

 

입력으로 주어지는 모든 수는 -263보다 크거나 같고, 263-1보다 작거나 같은 정수이다.

 

 

출력

첫째 줄부터 K줄에 걸쳐 구한 구간의 합을 출력한다. 단, 정답은 -263보다 크거나 같고, 263-1보다 작거나 같은 정수이다.

 

 

풀이

세그먼트 트리 입문용 문제였습니다. 혹시나 세그먼트 트리에 대해 모르시는 분은 아래 포스팅을 꼭! 꼼꼼하게 정독하시길 바랍니다.

 

 

41. 세그먼트 트리(Segment Tree)

 

 

위의 포스팅에서 사용한 init, sum, update도 그대로 구현합니다.

문제에서 a가 1일 경우 update 기능을, 2일 경우 sum 기능을 수행하도록 설계되었기때문이죠.

 

다만, 이 문제에서 주의해야할 부분이 2가지가 있습니다.

전자는 자료형이고, 후자는 dif 값 설정입니다.

 

문제에서 범위가 int 범위를 초과하는 수가 입력될 수도 있으므로 인덱스 탐색을 위한 변수를 제외하고, 자료형을 long으로 바꿔주셔야 합니다.

 

update 메소드에서 인자 dif는 원래의 수와 바꾸려는 수의 차이를 의미합니다.

따라서, 메인 함수에서 단순히 c를 dif로 넘기면 안 되고, c - arr[b]를 취해서 넘겨야 합니다.

다만, arr[b] = c로 초기화하는 과정을 잊으시면 안 됩니다.

 

마지막으로, 세그먼트 트리의 사이즈를 구하는 과정을 알아봅시다.

편하게 사이즈를 정하려면, 4 * N을 취해도 무방합니다만, 정석적인 방식도 설명하겠습니다.

 

위의 링크에서도 보셨다시피, N보다 작은 최대의 제곱수의 제곱을 취한 값이 세그먼트 트리의 사이즈라는 사실을 알 수 있었습니다.

 

즉, 2^k >= N인 최소의 k를 구해야 합니다.

양변에 log를 취하면, k >= logN / log2가 됩니다.

여기서 (logN / log2)의 값을 올림한 후, 1을 더해주면 N보다 작은 최대의 제곱수인 k를 구할 수 있습니다.

이제, k²를 취하면, 바로 세그먼트 트리의 사이즈가 됩니다.

 

 

아래는 위 과정을 정리한 소스코드입니다.

 

 

소스코드

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.