이동식 저장소

10999번: 구간 합 구하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 2042번 구간 합 구하기 1에서는 수가 하나씩 바뀌므로 세그먼트 트리 또는 펜윅 트리를 이용하여 문제를 풀 수 있다.. 그런데 이 문제에서는 $[l,~r]$ 구간의 값이 바뀐다. 따라서 일반적인 세그먼트 or 펜윅 트리를 이용해 값을 갱신하면 한 번의 갱신에 최대 $O(NlogN)$의 시간이 걸리고, 시간 초과를 받을 수밖에 없다. 일반적으로 쿼리 문제에서는 쿼리를 로그 시간 안에 해결해야 한다...