문제 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 풀이 solved.ac 난이도: Gold 1 부분합을 구하는 문제이지만 단순한 부분합 구현으로는 중간에 배열의 값이 바뀌면 다시 연속합을 구해줘야 하는 문제가 생긴다. 배열의 길이가 n이라면 중간에 바뀐 값으로 다시 연속합을 구하면 O(n)의 시간 복잡도가 소요된다. 해당 문제에서는 중간에 배열의 값 변경이 빈번히 일어나, 단순한 부..