문제

문제 링크 : https://www.acmicpc.net/problem/11659

풀이

문제에서 수열을 주고 구간의 합을 구하라고 하고 있다.

단순하게 하나하나 구하는 방법도 있지만, 이렇게 하면 최악의 경우 시간복잡도가 O(n^2)이 되기 때문에 시간 초과가 뜬다.

이럴 때 사용하는 방법이 누적 합(prefix Sum)이다. 누적 합을 사용하면 최악의 경우 시간 복잡도를 O(n)으로 만들 수 있다.

수열의 첫번째 요소를 리스트의 첫번째 항에, 첫번째~두번째 요소를 더한 값을 두번째 항에, 첫번째~세번째 요소를 더한 값을 세번째 항에 넣는 식으로 첫번째~n번째 요소를 더한 값을 리스트의 n번째 항에 넣어준다.

그 다음엔 i~j번째 수들의 합을 구해야하므로, j번째 누적합에서 i-1번째 누적합을 빼주면 된다.

만약 i가 1이라면 j번째 누적합이 i~j번째 수들의 합이므로 j번째 누적합을 출력해주면 된다.

import sys
input = sys.stdin.readline

n, m = map(int, input().split())

l = list(map(int,input().split()))

prefixSum = [0 for i in range(n)]
prefixSum[0] = l[0]

for i in range(1,n):
    prefixSum[i] = prefixSum[i - 1] + l[i]

for _ in range(m):
    i,j = map(int,input().split())
    if i == 1:
        print(prefixSum[j - 1])
    else:
        print(prefixSum[j - 1] - prefixSum[i - 2])