[python/파이썬] 백준 11659 구간 합 구하기 4

[문제 출처]

https://www.acmicpc.net/problem/11659

11659번: 구간 합 구하기 4

 

[소스 코드]

누적 합으로 푸는 문제이다.

arr[i]에는 i까지의 원소의 합이 저장되도록 하고, 

만일 i부터 j까지의 합을 구해야 한다면, arr[j]에서 arr[i-1]을 빼서 계산한다.

 

ex)

5 4 3 2 1

i = 2,  j = 4

5  5+4  5+4+3  5+4+3+2  5+4+3+2+1

2번째부터 4번째까지의 합은

arr[4] - arr[1]

(5+4+3+2) - (5) = 4+3+2 = 9

 

#11659
import sys

input = sys.stdin.readline

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

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

for i in range(1,n):
  arr[i] += arr[i-1]
arr = [0] + arr
for i in range(m):
  a,b = map(int, input().split())
  print(arr[b]-arr[a-1])