[C++] 누적합

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

구간 쿼리

배열이나 수열에서 특정 구간에 대한 합, 최댓값, 최솟값 등 특정 연산을 빠르게 구하는 문제를 말한다.

예제
수의 개수 N, 합을 구해야 하는 횟수 M, 그 이후 N개의 수가 주어진다. 수는 100 이하의 자연수. 그 이후 M개의 줄에는 합을 구해야 하는 구간 A, B가 주어진다. M개의 줄에 A부터 B까지의 합을 구하라.

• 1 <= N <= 100,000
• 1 <= M <= 100,000
• 1 <= A <= B <= N
• 수는 100이하의 자연수

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

typedef long long ll;

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;​
}

이렇게 구현하면 시간 복잡도가 100,000 * 100,000 = 10^10 으로 시간초과가 발생한다. 이럴 때 누적합을 사용해서 빠르게 답을 구할 수 있다.

누적합

배열의 각 원소를 순서대로 누적해서 저장한 배열을 의미한다. 이를 이용하면 구간 합을 O(1) 시간에 빠르게 계산할 수 있다.

int arr[] = {5, 2, 4, 7, 9};
int prefix[6];
prefix[0] = 0;
for(int i=1; i<=5; i++){
    prefix[i] = prefix[i-1] + arr[i-1];
}

i	arr[i-1]	prefix[i-1]	계산	prefix[i]
1	5	0	0 + 5	5
2	2	5	5 + 2	7
3	4	7	7 + 4	11
4	7	11	11 + 7	18
5	9	18	18 + 9	27

prefix의 첫번째 요소부터 누적합을 계산한다.
구간 [2, 4]의 합을 구한다면?
arr[2], arr[3], arr[4]의 합을 구해야한다.

int sum = prefix[5] - prefix[2];

27-7 =20 해주면 끝! 시간복잡도 O(1)만으로 구할 수 있다.