[백준] 11659번 구간 합 구하기 4 파이썬 코드

코드

# 누적합: 리스트의 각 원소에 대해 그 이전 원소들의 합을 미리 구하는 방법

# n = 100000, nlogn 이하로 구하자
# sum 함수의 시간복잡도는 O(N), 긴 시퀀스를 구할 때는 시간이 오래걸린다.
# 아래 방법은 O(N+M)으로 해결할 수 있다.

import sys
input = sys.stdin.readline

n,m = map(int, input().split())
score = [*map(int, input().split())]

temp = 0
arr = [0] # 제로인덱스임을 감안해서 0 추가
for i in score:
  temp += i # 구간합
  arr.append(temp)
for _ in range(m):
  x,y = map(int, input().split())
  print(arr[y]-arr[x-1])

dp로 해결하려했는데 시간초과가 났던 문제... 구간 합이라는 분류가 있다는 것을 처음 알게 되었다.