[C++] 누적합

귀여움 누적

누적합이란?

요소들의 누적된 합.

어떠한 배열을 기반으로 앞에서부터 요소들의 누적된 합을 저장해 새로이 배열을 만들어 활용하는 것을 의미한다.

앞에서부터 더하는 prefix sum, 뒤에서부터 더하는 suffix sum이 있는데, 코딩테스트에는 prefix sum이 자주 나온다.

 

누적합을 만들 때, 0번째 index는 비워두고 1번째 index부터 사용하는 것이 편하다

인덱스	0	1	2	3	4
원소	0	1	10	11	100
누적합	0	1	11	22	122

 

누적합을 C++로 간단하게 구현할 수 있다.

#include <bits/stdc++.h>

using namespace std;

int a[100004], b, c, psum[100004], n, m;

int main() {
    cin >> n >> m;

    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }

    for (int i = 0; i < m; ++i) {
        cin >> b >> c;
        int sum = 0;
        for (int j = b; j <= c; ++j) {
            sum += a[j];
        }
        cout << sum << "\n";
    }
    
    return 0;
}

하지만 n과 m의 최대 범위가 100,000인 문제라면 위 코드의 시간 복잡도는 100억(10만*10만)이 된다.

그렇기 때문에 다른 방법이 필요하다.

 

구간합은 위 사진과 같이 두 Psum(첫 원소부터의 누적합)의 차로 표현할 수 있다.

이를 통해 100억(10만*10만)이였던 시간 복잡도를 10만(10만*1)으로 줄일 수 있다.

#include <bits/stdc++.h>

using namespace std;

int a[100004], b, c, psum[100004], n, m;

int main() {
    cin >> n >> m;

    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        psum[i] = psum[i-1] + a[i]; // ex) psum[3] = psum[2] + 3
    }

    for (int i = 0; i < m; ++i) {
        cin >> b >> c;
        cout << psum[c] - psum[b-1] << "\n";
    }
    
    return 0;
}

배열의 요소들이 변하지 않는 정적 배열일 때는 누적합, 요소들이 변하는 동적 배열일 때는 펜윅트리를 사용해서 해결한다.

 

Reference

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트 - 인프런 | 강의