[알고리즘] 구간 합 구하기

*구간 합 알고리즘이 필요한 이유

• 구간마다 합을 매번 계산하게 되면 계산해야하는 양이 많아지면 시간초과가 발생할 수 있다. 실제 코딩테스트에서 사용 빈도가 많이 높다 

*구현 원리

합배열을 미리 만들어 놓으면 큰 구간에서 작은 구간을 빼면 두 구간 사이의 합이 나옴을 이용 

ex)1번부터 3번까지의 합은 sum[3]-sum[1]임을 이용

*구현 방법

1. 입력받은 숫자의 합배열을 생성한다
2. 합배열에서의 특정 구간을 값을 S[j]-S[i-1]로 계산한다.

*구현 코드

#예시문제 백준 11659번
import sys
input =sys.stdin.readline

N,M= map(int ,input().split()) #숫자의 수 N, 구간 합 출력 수 M 입력
numbers=list(map(int, input().split()))# 숫자들 저장
sum_list=[0]#합배열을 만들기 위해 리스트 생성
tmp=0
for i in numbers: #합배열 만들기
    tmp+=i
    sum_list.append(tmp)

for i in range(M): #계산결과 출력 
    i,j = map(int ,input().split())
    print(sum_list[j]-sum_list[i-1])