[백준 11659] 구간 합 구하기 4
문제 : https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N (1 ≤ N ≤ 100,000), 합을 구해야 하는 횟수 M (1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다. www.acmicpc.net 2019/08/07 - [PS/Tip] - [C++/STL] 부분 합 partial_sum( ) [C++/STL] 부분 합 partial_sum( ) 특정 구간의 합을 O(1)에 구하고 싶을 때, 부분 합(partial sum)을 미리 구해놓으면 가능하다. 부분 합은 다음과 같다. i 0 ..