BOJ11659-구간 합 구하기4 (python3)

그냥 처음 떠오른 생각대로 직관적으로 풀면
시간초과 오답을 벗어날 수 없다.
질문게시판을 통해 누적합을 이용하기로 하였다.

누적합은 입력된 숫자들의 리스트를 한번만 돌면서 차곡차곡 더할때마다 리스트에 넣어주는 것이다.

5~8의 합을 구할때 5+6+7+8 은 1~8까지 더한 값에서 1~4까지 더한값을 빼는 것과 같다는 것을 이용하여 풀면 시간복잡도를 훨씬 줄일 수 있다.

import sys
n,m = map(int, sys.stdin.readline().split())
n_list = list(map(int,sys.stdin.readline().split()))
sum_list = [0]
sum, j = 0,0
for i in n_list:
    sum += i
    sum_list.append(sum)
while m>j:
    start, end = map(int,sys.stdin.readline().split())
    print(sum_list[end]-sum_list[start-1])
    j += 1