20. 누적합

누적합

빠른 설명

누적합은 앞에서부터 합을 미리 저장해 두고, 구간 합을 빠르게 구하는 기법이다.

언제 쓰는가

• 구간 합 질의가 여러 번 나올 때
• 배열을 매번 다시 더하면 시간 초과가 날 때
• 2차원 격자에서 직사각형 합을 구할 때

시간복잡도

• 전처리: $O(N)$
• 구간 합 질의: $O(1)$

참고자료

• Wikipedia - Prefix sum
• USACO Guide - Prefix Sums
• GeeksforGeeks - Prefix Sum Array

C++ 코드

#include <algorithm>
#include <deque>
#include <functional>
#include <iostream>
#include <queue>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;
 
int main() {
    vector<int> a = {2, 4, 1, 3, 5};
    int n = a.size();
    vector<int> prefix(n + 1, 0);
 
    for (int i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] + a[i];
    }
 
    int l = 1, r = 3; // a[1]부터 a[3]까지
    cout << prefix[r + 1] - prefix[l] << '\n';
}

Python 코드

a = [2, 4, 1, 3, 5]
prefix = [0]
 
for x in a:
    prefix.append(prefix[-1] + x)
 
l, r = 1, 3
print(prefix[r + 1] - prefix[l])