35 lines
807 B
Python
35 lines
807 B
Python
# 구간 합 구하기4
|
|
|
|
import sys
|
|
|
|
input = sys.stdin.readline
|
|
def input_ints():
|
|
return map(int, input().rstrip().split())
|
|
|
|
def solution():
|
|
n, m = input_ints()
|
|
|
|
lst = [0]+list(input_ints())
|
|
|
|
prefix_sum = lst[:]
|
|
for i in range(1, n+1):
|
|
prefix_sum[i] = prefix_sum[i-1]+lst[i]
|
|
|
|
for _ in range(m):
|
|
i, j = input_ints()
|
|
print(prefix_sum[j]-prefix_sum[i-1])
|
|
|
|
|
|
return
|
|
|
|
|
|
solution()
|
|
|
|
"""
|
|
걸린 시간: 9분
|
|
|
|
시간 복잡도: 누적합 리스트를 채우는데 O(n)이 걸린다.
|
|
|
|
해설: 구간 합을 m번 계산해야하는데, m이 100,000이하이므로 썼던 것을 재활용하지 않으면 시간초과가 날 것 같았다.
|
|
구간합은 누적합 - 누적합으로 계산할 수 있기 때문에 누적합을 처음에 계산해놓고 진행했다.
|
|
""" |