Prefix Sums

누적합 혹은 부분합을 구할 때 사용하는 알고리즘.

 

누적합: A[0] + A[1] + ... + A[N]

0번째부터 N번째까지, 모든 값을 더하면 된다.

배열A	A[0]	A[1]	A[2]	A[3]	A[4]	A[5]	A[6]	A[7]	A[8]	A[9]
	6	5	4	1	2	3	7	9	8	1
누적합	6	11	15	16	18	21	28	37	45	46

 

---

누적합 활용

누적합은 구간합을 구할 때, 사용할 수 있다.

아래의 그림에서 C 구간의 값을 구해보자.

정답은: A \( - \) B 이다.

 

\( A = A[0] + ... + A[9] \)

\( B = A[0] + ... + A[3] \)

\( C = A[4] + ... + A[9] \)

\( \therefore C = (A[0] + ... + A[9]) - (A[0] + ... + A[3]) = 46 - 16 = 30\)

 

---

누적합 활용 이유

속도가 빠르다.

반복문을 이용해서 부분합을 구하면 \( O(n) \)의 시간이 필요하다.

하지만 누적합을 이용하면 \( O(1) \)의 시간만 있으면 된다.

 

---

누적합 구현

누적합 배열을 별도로 하나 만들면 된다.

 

 

첫번째 방법

배열과 누적합 배열의 크기를 똑같이 만든다.

배열A	A[0]	A[1]	A[2]	A[3]	A[4]	A[5]	A[6]	A[7]	A[8]	A[9]
	6	5	4	1	2	3	7	9	8	1
누적합	6	11	15	16	18	21	28	37	45	46

 

 

두번째 방법

누적합 배열의 크기를 더 크게(+1) 만든다.

누적합 배열을 더 크게(+1) 만든다

 

두 방법의 차이는 부분합을 구할 때, 나타난다.

A[4]에서 A[9]까지의 부분합을 구해보자.

첫번재 방법: \( A[9] - A[3] \)

두번째 방법: \( A[10] - A[4] \)

 

즉, M(4) ~ N(9) 구간의 부분합을 구한다고 했을 때,

첫번째 방법: 누적합[N] \( - \) 누적합[M-1]

두번째 방법: 누적합[N+1] \( - \) 누적합[M]

---

코드 (C++)

아래는 두번째 방법을 구현한 코드이다.

출력: 0 1 3 6 10 15

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    vector<int> A = { 1, 2, 3, 4, 5 };
    vector<int> P(A.size() + 1, 0);

    int n = static_cast<int>(A.size());

    for (int i = 1; i <= n; i++)
    {
        P[i] = P[i - 1] + A[i - 1];
    }

    for (const auto v : A) cout << v << ' '; cout << endl;
    for (const auto v : P) cout << v << ' '; cout << endl;

    cout << endl;

    return 0;
}