수열의 구간 합을 빠르게 계산하는 방법1 -접두사 합(prefix sum)-

1. 개요

 

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

 

예를 들어 [10,20,30,40,50]이 있다고 가정해보자. 두번째 수부터 네번째 수까지의 합은 20+30+40=90이다.

 

이러한 구간 합 계산 문제는 매우 간단하게 인덱싱으로 구할 수 있을 것 같지만,

 

여러개의 테스트 케이스로 구성된 문제라면 이야기가 달라진다

 

T개의 테스트 케이스가 주어지고 테스트케이스 각각이 [left,right]에 존재하는 모든 수의 합을 구하라고 한다고 하자

 

만약 수열의 길이가 N이라고 한다면, 최악의 경우 O(NT)의 시간복잡도를 가진다

 

매 테스트케이스마다 길이 N의 구간합을 계산하라고 할 수 있기 때문이다.

 

하지만 만약 N=1000000이고 T=1000000이라고 한다면? O(NT)로는 문제를 해결하기에는 어림도 없다

 

하지만 여러 번 사용될 만한 정보는 미리 구해 저장해놓는다면 어떨까?

 

테스트 케이스는 T개로 변경되겠지만, N개의 수는 매 케이스마다 변경되지 않는다

 

N개의 수에 대해 어떤 처리를 적절하게 해놓고, 각 테스트 케이스마다 한번에 구간합을 도출해서 내놓는다면?

 

 

2. 접두사합(prefix sum)

 

구간 합 계산을 위해 가장 많이 사용되는 기본적인 기법은 접두사 합(prefix sum)이다.

 

예를 들어 다음과 같이 5개의 데이터가 있다고 해보자

 

10, 20,30,40,50

 

배열 P[i+1]이 0~i까지의 누적합이라고 정의하자

 

그렇다면

 

P[0] = 0

 

P[1] = 10

 

P[2] = 10+20 =30

 

P[3] = 10+20+30 = 60

 

P[4] = 10+20+30+40 = 100

 

P[5] = 10+20+30+40+50 = 150

 

만약 구간 [L,R]의 수열 합은 어떻게 구할 수 있을까?

 

P[R+1] - P[L]의 단 1번의 계산만으로 가능하다

 

예를 들어 [1,3]의 수열 합은 20+30+40이다

 

그런데 P[4] = 10+20+30+40이고 P[1] = 10이다.

 

따라서 P[4]-P[1] = 20+30+40이다.

 

이러면 매 테스트케이스마다 O(1)의 시간으로 구간합을 구할 수 있다

 

3. 구현 예시

 

인덱스를 어떻게 설정하느냐에 따라 달라질 수 있고 실수하기도 쉽다

 

잘 생각하면서 구현해야겠다

 

시간복잡도는 O(N+T)가 된다. N만큼 순회하여 prefix sum을 구하고, T만큼 순회하여 매 케이스마다 답을 낸다.

 

핵심은 누적합 배열을 계산하고,

 

right까지 누적합에서 left까지 누적합을 빼주면, 해당 left에서 right까지 부분구간의 합만 얻을 수 있다는 점이다.

 

#데이터의 개수 n과 전체 데이터

n = 5

data = [10,20,30,40,50]

#접두사 합 배열 계산
#누적합을 계산하면 된다

sum_value = 0
prefix_sum = [0]

for i in range(5):
    
    sum_value += data[i]
    prefix_sum.append(sum_value)

#테스트 케이스마다 구간합 출력

T = 3

for _ in range(T):
    
    l,r = map(int,input().split())

    print(prefix_sum[r+1]-prefix_sum[l])
"""
1 3
90
2 4
120
3 4
90
"""