알고리즘
PrefixSum 갱신 빠르게 하기
문제 2268번: 수들의 합 7 첫째 줄에는 N(1 ≤ N ≤ 1,000,000), M(1 ≤ M ≤ 1,000,000)이 주어진다. M은 수행한 명령의 개수이며 다음 M개의 줄에는 수행한 순서대로 함수의 목록이 주어진다. 첫 번째 숫자는 어느 함수를 사용했는 www.acmicpc.net 재정의 PrefixSum(구간 합)과 갱신을 하는 단순한 문제. N이 10**6이고, M이 10**6이다. O(n*log n)으로 풀어야 한다. M번 만큼의 loop는 무조건 돌아야 하므로, PrefixSum, Update를 O(log n)이하로 풀어야 한다. 누적합을 이용하면 O(1)로 PrefixSum을 구할 수 있다. 하지만 update하는데 O(n)이 들기 때문에, 누적합을 활용할 수 없다. O(log n)으로 ..
