[알고리즘] 누적합 알고리즘

누적합 (Prefix sum)

누적합은 나열된 수의 누적된 합을 나타낸다.

Sn은 An[0,0] 합, An[0,1]합, An[0,2]합 An[0,-1]합 을 나타낸다.

누적합의 점화식은 Sn = Sn-1 + An 이다.

 

위 그림은 인덱스가 0부터 4까지의 수열과 해당 수열의 누적합을 나타낸 이미지 이다.

누적합을 이용해서 인덱스가 2부터 4까지의 구간을 구하려면 [0부터 4까지의 누적합](녹색) - [0부터 1까지의 누적합](빨강색) 을 계산하면 된다. 

즉, 구하고 싶은 구간은 보라색이며 누적합 0부터 4까지의 구간에서 빨강색 구간을 빼면 구할 수 있다.

누적합15-누적합3 = 12 (2부터 4까지의 구간)

 

인덱스가 2부터 4까지의 구간을 구하려면 2부터 4까지 인덱스를 돌면서 카운트 할 수 있겠지만 이렇게 하면

N개 구간에서 M개의 구간합을 구하는 경우 시간복잡도는 O(NM) = O(N^2) 이 된다.

 

그러나 누적합을 이용해서 구하면 시간복잡도를 O(N+M) = O(N) 까지 줄일 수 있다.

 

이미지 출처: https://sskl660.tistory.com/77

누적합의 집합을 Sn이라고 한다면 구간 [i , j] 의 구간합은 Sj와 Sj-1을 뺀 값으로 구할 수 있다.

Sn 까지의 구간합을 구해놓으면 이후 구간합을 구하는 연산은 O(1)시간이면 구할 수 있어

O(N+M)의 시간 복잡도를 가지게 된다. 

 

누적합 알고리즘 구현

def prefix_sums(A):
    n = len(A)
    P = [0] * (n + 1)
    for k in xrange(1, n + 1):
    	P[k] = P[k - 1] + A[k - 1]
    return P

A: 수열, P: 누적합 수열을 나타냄.

 

관련문제

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

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

 

참고

https://jow1025.tistory.com/47

https://codility.com/media/train/3-PrefixSums.pdf