누적합(Prefix Sum) 이란?

누적합이란?

수열 A[1], A[2], A[3], ..., A[N]이 있을 때 A[i] + ... + A[j] 의 구간의 누적합을 구하는 문제입니다.

일반적으로 모든 배열을 돌면서 누적합을 구한다면 시간복잡도는 O(n^2) 입니다. 

시간복잡도를 O(n)으로 해결하기 위해서는 누적합(Prefix Sum)을 이용하여 문제를 해결할 수 있습니다.

즉 i번째수까지 전부 구한 값을 구하고자 한다면 첫번째 수부터 i번째까지 수까지 누적하여 더해준 값을 이용하면 됩니다.

=> S[i] = A[1] + A[2] + A[3] + A[i-1] + ... + A[i] = S[i-1] + A[i] 

 

 

다음과 같은 배열이 있을 경우 누적합은 다음과 같습니다.

i	0	1	2	3	4
A[i]		2	-2	2	-2
S[i]	0	2	0	2	0

 

만약 i = 2 부터 3까지인 구간합을 구하려면 A[2] = -2, A[3] = 2 이므로 이를 더해주면 0 이라는 것을 알 수 있습니다.

이를 구간합을 이용하면 S[3]  = 2, S[1] = 2 이고 이를 빼주면  구간합을 구할 수 있습니다.

그 이유는 아래 그림을 참고하시면 됩니다.

 

시간복잡도는 O(n)과 같은데,

S[i] = A[1] + A[2] + A[3] + A[i-1] + ... + A[i] 이고

이는  S[i] = S[i-1] + A[i]  와 같기때문입니다. ( S[i-1] = A[1] + A[2] + A[3] + A[i-1] 이므로)