누적합

문제 링크 https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 문제 풀이 N, M이 각각 10만까지로 만약 범위를 입력받을 때마다 해당 구간에 대해 더하는 연산을 통해 답을 도출한다면 O(NM)의 시간복잡도로 시간초과가 나게됩니다. 매번 합을 도출하는 것이 아니라, 처음에 입력받은 리스트에 대해 누적합을 미리 저장해놓은 후, 만약 i부터 j 인덱스까지의 범위를 구하고 싶을 경우 [ j까지의 누적합 - (i - 1)까지의 누적..