누적합(Prefix Sum)

누적합(Prefix Sum)

누적합은 요소들의 누적된 합의 의미를 얘기합니다.

배열의 첫 번째 0번째 배열의 요소부터 누적시키면서 더한 배열을 활용합니다.

 

일부 구간에 대한 합을 구하는 문제에서 사용이 됩니다. 단, 배열의 값들이 변하지 않는다는 전제가 필요합니다.

 

$ N = 5 $ 인 N 크기의 정수 배열 arr이 있을 때 여러 개의 구간 [a, b]에 대해 합을 구하려고 합니다. $ 1\leq a\leq b\leq N $

$$ arr[a]+arr[a+1]+\cdots+arr[b] $$

Index i	0	1	2	3	4
arr[i]	1	6	4	2	5

 

간단하게 생각할 수 있는 방법은 반복문을 돌려서 각 요소를 더하는 것입니다. 이 방법은 각 쿼리에 대해 최대 $ O(N) $ 시간 복잡도를 가지고, 만약 M개의 쿼리가 주어지면 시간 복잡도는 $ O(N * M) $가 되게 됩니다. 이 방식은 N, M 범위가 최대 100,000일 때 $ O(N * M) = 10^{10}$ 100억으로 시간 초과할 가능성이 매우 높습니다. 이럴 때 누적합 알고리즘을 사용합니다.

$$ prefix[k] = \sum_{i=1}^{k}arr[i] $$

$$ prefix[k] = prefix[k - 1] + arr[k] $$

Index i	0	1	2	3	4	5
prefix[i]	0	1	7	11	13	18

 

[a, b]의 구간 합을 구하는 공식은 다음과 같습니다.

$$ \sum_{i=L}^{R}arr[i] = \sum_{i=1}^{R}arr[i] - \sum_{i=1}^{L-1}arr[i] $$

$$ \sum_{i=L}^{R}arr[i] = prefix[R] - prefix[L - 1] $$

 

이렇게 빼기만 하면 [a, b]의 구간 합을 구할 수 있기 때문에 $ O(1) $ 시간 복잡도가 걸리게 되고, 구간에 대한 반복문을 돌리는 $ O(N) $보다 빠르게 구할 수 있습니다. 만약 M개의 쿼리가 주어진다면 누적합 배열을 만드는 $ O(N) $과 M개의 쿼리는 처리하는 $ O(1) $, 그래서 최종적으로 $ O(N + M) $ 시간 복잡도가 되게 됩니다.

 

$ a = 2, b = 4 $로 가정하고 구해보겠습니다. 식은 다음과 같습니다.

$$ \sum_{i=2}^{4}arr[i] = 6 + 4 + 2 = 12 $$

Index i	1	2	3	4	5
arr[i]	1	6	4	2	5

 

누적합으로 다음과 같이 구할 수 있습니다.

$$ prefix[4] - prefix[1] = 13 - 1 = 12 $$

Index i	0	1	2	3	4	5
prefix[i]	0	1	7	11	13	18

 

Index를 왜 0이 아닌 1부터 사용하는지 궁금할 수 있습니다. 그 이유는 공식에서 보던 것과 같이 누적합의 배열을 만들기 위해서 "이전 값과 현재 값을 더한 값을 현재 Index에 넣어줘야 하기 때문입니다." 1번째 배열부터 시작해서 반복문으로 prefix[i] = prefix[i - 1] + arr[i]로 접근하기가 더 쉬워집니다.

 

누적합 구현(C++)

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

int N = 6, arr[] = {0, 1, 6, 4, 2, 5}, ps[6], a = 2, b = 4;
int main() {
    for (int i = 1; i < N; i++) {
        ps[i] = ps[i - 1] + arr[i];
    }

    cout << ps[b] - ps[a - 1] << "\n"; // 12
    return 0;
}

 

입력 값을 받아서 할 때는 아래와 같습니다.

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

int arr[100004], ps[100004], n, m, a, b;
int main() {
	cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
        ps[i] = ps[i - 1] + arr[i];
    }
    for (int i = 0; i < m; i++) {
        cin >> a >> b;
        cout << ps[b] - ps[a - 1] << "\n";
    }
    return 0;
}
/*
5 3
1 6 4 2 5
1 4
2 4
3 5

13
12
11
*/

 

Suffix Sum

Suffix Sum은 Prefix Sum과 반대로 앞에서부터 누적합을 하는 게 아니라 맨 끝부터 누적합을 하면 됩니다.

 

 

 

🔗 Reference

• LaTex 수식 온라인 에디터
• 10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
• [알고리즘 강의] 1주차. 시간복잡도, 빅오표기법, 공간복잡도, 누적합, 구현