[백준 11659번] 누적 합 알고리즘-파이썬(python)

구간 합 구하기 4 

문제

수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.

 

출력

총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.

 

제한

• 1 ≤ N ≤ 100,000
• 1 ≤ M ≤ 100,000
• 1 ≤ i ≤ j ≤ N

---

예제 입력 1

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

---

예제 출력 1

12
9
1

---

누적 합(Prefix Sum) / 구간 합

누적합 또는 구간 합 알고리즘은 코딩테스트에 사용 빈도가 높은 알고리즘이기 때문에 꼭 알아두면 좋습니다.

구간 합은 합 배열을 만들고, 재사용해서 시간 복잡도를 줄이는 알고리즘입니다.

고등학교 수1-수열에서 a1 ,a2...ai 가 수열의 일반항이고, S1,S2.....Sn가 수열의 합을 나타냈습니다.

똑같이 배열에서 A[0] + A[1] + .... A[n] 까지 더한것을 S[n]에 저장하고 불러오는 것입니다.

 

정의 : S[i] = A[0] + A[1] + .... A[i]

 

A[i] + ....+ A[j] 를 S[j] - S[i-1] 라는 간단한 연산으로 바로 구할 수 있습니다.

 

A[i] 부터 A[j]까지의 리스트를 합배열 없이 구하는 경우, 최악의 경우 0~N 인경우로 시간 복잡도는 O(N)입니다.

그러나 합 배열을 이용하면 O(1)안에 답을 구할 수 있습니다.

 

합 배열을 만드는 공식 : S[i] = S[i-1] + A[i]

 

입력에서 항을 하나씩 받을 때마다 기존의 합배열에 하나씩 추가하는 방법으로 진행 할수 있습니다.

---

파이썬 코드

수의 입력을 numbers에 받고 계속 합해 가면서 s배열을 만듭니다.

그리고 입력 i,j가 주어질때마다 공식을 이용해서 출력합니다.

#누적합
import sys
input = sys.stdin.readline
size , quizNum = map(int , input().split())
numbers = list(map(int , input().split()))
temp =0
s = [0]
for i in numbers:
    temp+=i
    s.append(temp)
for x in range(quizNum):
    i,j = map(int , input().split())
    print(s[j]-s[i-1])