[문제] https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net [풀이] 누적 합 누적 합은 구간의 누적 합을 구하는 문제이다. 일반적으로 리스트에 값을 저장하고, 인덱스로 한개씩 더하는 방식은 최악의 경우 O(n^2)의 시간복잡도를 갖기 때문에 입력의 범위가 클 때는 사용할 수 없다. 하지만 Prefix sum 방식을 사용하면 O(n)의 시간복잡도로 해결할 수 있다. 누적합은 문제에서 수열이 주어지고 어떤 구간의 값의 합을 구..
