https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 첫번째 시도 : 누적 합 + HashMap 제목을 보고 가장 먼저 떠올린 것이 누적 합이었다. 수열을 받으면서 동시에 이전 누적값을 계속 더해준다면 a부터 b 사이 구간합을 구할 때 sum[b] - sum[a - 1] 로 바로 구할 수 있기 때문이다. 하지만 이 문제처럼 중간에 값이 바뀔 때마다 누적 합을 다시 구한다면 최대 N * K (..
