[알고리즘] 누적 합 (Prefix Sum)

누적 합(Prefix Sum)

배열의 처음부터 정해진 위치까지의 합.

누적 합을 미리 계산하면 배열의 특정한 범위의 합계를 바로 구할 수 있다.

 

길이가 N인 배열의 누적 합을 구하는 과정의 경우 시간 복잡도는 O(N).

누적 합을 통해 배열의 특정 구간[L, R]의 합을 구할 때 시간 복잡도는 O(1).

→ Q번의 질의가 있는 경우, O(N)+O(Q)이므로 시간 복잡도는 O(N+Q).

 

만약 누적 합을 사용하지 않는 경우, 특정 구간의 합을 구하는 시간 복잡도는 O(N)이며, 특히 Q번의 질의가 있는 경우 시간 복잡도는 O(NQ).

---

과정

원본 배열 A가 아래의 표와 같다고 해보자.

1

4

2

3

5

 

A의 누적 합 배열 P는

P[0] = A[0] = 1
P[1] = A[0] + A[1] = 1 + 4 = 5
P[2] = A[0] + A[1] + A[2] = 1 + 4 + 2 = 7
P[3] = A[0] + A[1] + A[2] + A[3] = 1 + 4 + 2 + 3 = 10
P[4] = A[0] + A[1] + A[2] + A[3] + A[4] = 1 + 4 + 2 + 3 + 5 = 15

 

이므로 아래의 표와 같이 나타낼 수 있다.

1

5

7

10

15

 

---

구현 (C++)

#include <bits/stdc++.h>
using namespace std;

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

    P.push_back(A[0]); // A의 1번 요소를 P.begin()에 push.

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

    for (auto j : P)
    {
        cout << j << " ";
    }
    return 0;
}

 

---

응용 - 차분 배열(Difference Array)

예를들어 다음과 같은 문제가 있다고 해보자.

이 문제는 누적 합을 이용하는 문제이지만, 참가자에 따라 참가하는 일수가 다르기 때문에 (= 구간의 업데이트가 빈번한 문제이기 때문에) 두 원소의 차이를 저장하는 새로운 배열을 만들고, 그 배열의 누적 합을 구하여 더 빠르게 구할 수 있는 테크닉을 보일 수 있다.

 

아래는 구현 예시이다.

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int D, N, L, R;
    cin >> D;
    cin >> N;
    vector<int> change(D + 1, 0);

    for (int i = 0; i < N; i++)
    {
        cin >> L >> R;
        change[L - 1]++;
        change[R]--;
    }

    vector<int> result;
    result.resize(D);
    result[0] = change[0];
    for (int i = 1; i < D; i++)
    {
        result[i] = result[i - 1] + change[i];
    }

    for (auto i : result)
    {
        cout << i << " ";
    }

    return 0;
}

 

위 코드에서 change는 각 위치에서 몇 층을 올라가거나(-1이면 내려가거나) 해야 하는지를 알려주고 result는 실제로 그 층계를 따라가면서 현재 몇 층에 있는지를 기록한다고 볼 수 있다.

 

(또한 예시 문제는 inchworm algorithm으로도 풀 수 있다.)