[알고리즘] 누적합(Prefix Sum)

오랜만에 PS(Problem Solving)관련된 글입니다. 

최근에 백준을 안 풀다보니 실력이 많이 떨어진것 같아서 다시 복습하는 겸 

주기적으로 알고리즘을 정리해볼까 합니다. 

 

이번 글은 시작이다보니 쉬운 것부터 해보겠습니다. 

이번 글에서 다룰 내용은 누적합(Prefix Sum)입니다. 

 

정의 

• 어떤 수열 A에 대해서 처음부터 각 인덱스까지의 요소들의 합을 미리 구해놓는 알고리즘 

 

누적합을 생성할 때 사용되는 점화식은 아래와 같습니다.

\(PrefixSum[i] = PrefixSum[i - 1]  + A[i]\)

• PrefixSum(누적합의 결과 배열), i(현재 인덱스)  

 

구간합 구하기 

누적합의 가장 기본적인 활용법은 구간의 합을 구하는 것입니다. 

구간의 합을 구하는 것은 아래의 식을 통해서 할 수 있습니다. 

\(ret = P[end] - P[start - 1]\) 

• P(누적합 배열), start(시작 인덱스), end(끝 인덱스)

 

구현 

#include <vector>

vector<int> v;
int p[101];

int main() {
	int n; cin >> n;
	for (int i = 1; i <= n; i++) {
		int x; cin >> x;
		v.push_back(x);
		p[i] = p[i - 1] + x;
	}
}

 

 

 

이상으로 누적합에 대한 내용을 마치겠습니다. 

읽어주셔서 감사합니다.