[BOJ] 백준 2268번 : 수들의 합 (JAVA)

문제

N개의 수 A[1], A[2], …, A[N] 이 주어졌을 때, 함수 Sum(i, j)는 A[i]+A[i+1]+…+A[j]를 구하는 함수이다. (i>j일 경우에는 A[j]+A[j+1]+...+A[i]) A가 주어졌을 때, Sum(i, j)를 구하는 것은 매우 쉬운 문제이다. 이러한 (i, j)가 여러 개 주어졌을 때도 별로 어려운 문제는 아니다.

 

 

Sum함수와 더불어 Modify라는 함수를 정의하자. Modify(i, k)를 수행하면 A[i]=k가 되는 함수이다. Sum함수와 Modify 함수의 사용 목록이 주어졌을 때, 이에 해당하는 연산을 하는 프로그램을 작성하시오. 두 함수를 섞어서 사용할 수도 있다.

입력

 

 

첫째 줄에는 N(1≤N≤1,000,000), M(1≤M≤1,000,000)이 주어진다. M은 수행한 명령의 개수이며 다음 M개의 줄에는 수행한 순서대로 함수의 목록이 주어진다.

 

첫 번째 숫자는 어느 함수를 사용했는지를 나타내며, 0일 경우에는 Sum 함수를, 1일 경우에는 Modify 함수를 나타낸다. 다음 두 수는 각 함수의 인자 (i, j)나 (i, k)를 나타낸다. 처음에는 A[1]=A[2]=…A[N]=0이다. Modify인 경우에 1 ≤ k ≤ 100,000 이다.

 

 

출력

Sum 함수의 개수만큼 각 줄에 Sum 함수의 리턴값을 출력한다.

 

 

풀이

세그먼트 트리 기초 문제였습니다.

 

세그먼트 트리에 대해 모르시는 분은 아래 포스팅을 정독하시길 바랍니다.

 

 

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

 

 

다만, '2042번 구간 합 구하기'와는 달랐던 점은 update 부분이었습니다. 이 문제는 특정 값을 더해 나가는 것이 아닌, 특정 값을 다른 값을 변경시키기때문에 리프 노드를 먼저 다른 값으로 변경시킨 후, 리프 노드와 연결된 트리의 가지 전체의 구간합을 업데이트해야 합니다.

 

 

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

 

 

소스코드

 

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