Prefix Sum

구간 합(prefix sum)

특정 구간[s, e]의 합을 O(1) 시간안에 구할 수 있도록 미리 누적된 배열 합 p 를 구해놓는 방법이다.

배열의 시작 인덱스가 0임을 고려해, 크기를 1 늘려주어 사용하는 편이 깔끔하다.

p[e] - p[s-1] 으로 계산할 수 있다.

C++

#include <iostream>
#include <vector>
using namespace std;

void main(){
    int n = 5;
    vector<int> a = {1, 2, 3, 4, 5};
    vector<int> p(n+1, 0);
    p[1] = a[0];
    for(int i = 2; i <= n; i++)
        p[i] = p[i-1] + a[i-1];
    int s = 3;
    int e = 4;
    cout << p[e]-p[s-1] << "\n"; // 3 + 4 = 7
    return 0;
}