[이론] 구간 합(Prefix sum)

구간 합 문제

: 연속적으로 나열된 n개의 수가 있을 때, 특정 구간의 모든 수를 합한 값을 구하는 문제

- m개의 쿼리, 매번 구간 합을 계산하면 => O(NM)

 

구간 합 빠르게 계산하기 알고리즘 

- N개의 수에 대해서 어떠한 처리를 수행한 뒤에 나중에 M개의 쿼리가 각각 주어질 때마다 빠르게 구한 합을 도출할 수 있도록 하면 어떨까? => 접두사 합 이용(Prefix sum) =>O(N+M) 

- 각 쿼리에 대해 구간합을 빠르게 개선하기 위해서는 n개의 수의 위치 각각에 대하여 접두사 합을 미리 구해 놓으면 된다 =

EX) [10,20,30,40,50] => [0,10,30,60,100,150] 3~4 100-30=70

1.  N개의 수에 대하여 접두사 합 (Prefix Sum)을 계산하여 배열 P에 저장한다 2.  매 M개의 쿼리 정보[L,R]을 확인할 때, 구간 합은 P[R]-P[L-1]

#접두사 합을 활용한 구간 합
#
import sys
sys.stdin = open("input.txt","r")
n=5
data=[10,20,30,40,50]

#접두사 합 계산
sum=0
prefix_sum=[0]
for i in data:
    sum+=i
    prefix_sum.append(sum)
#구간 합 계산(세번째 수부터 네번째 수까지 구하기
left =3
right = 4
print(prefix_sum[right]-prefix_sum[left-1])