누적합

누적합

• 요소들의 누적된 합의 의미
• 어떠한 배열을 기반으로 앞에서 부터 요소들의 누적된 합을 저장해 새로 배열을 만들어 활용하는 것
• 앞에서 부터 더하는 Prefix Sum, 뒤에서 부터 더하는 Suffix Sum이 있지만 Prefix Sum을 만이 사용한다
• 예제 문제

예시문제
승철이는 뇌를 잃어버렸다.
학교에 갔더니 선생님이 자연수로 이루어진  N개의 카드를 주며 M개의 질문을 던진다. 
그 질문은 나열한 카드 중 A번째부터 B번째까지의 합을 구하는 것이다. 
뇌를 잃어버렸기 때문에 승철이는 이 문제를 풀 수 없다. 문제를 풀 수 있는 프로그램을 작성해보자.  

입력
수의 개수 N, 합을 구해야 하는 횟수 M, 그 이후 N개의 수가 주어진다.
수는 100 이하의 자연수. 그 이후 M개의 줄에는 합을 구해야 하는 구간 A, B가 주어진다. 

출력
M개의 줄에 A부터 B까지의 합을 구하라. 

범위
1 <= N <= 100,000
1 <= M <= 100,000
1 <= A <= B <= N  

예제입력
8 3
1 2 3 4 5 6 7 8
1 4
1 5
3 5
에제출력
10
15
12
[출처] [알고리즘 강의] 1주차. 시간복잡도, 빅오표기법, 공간복잡도, 누적합, 구현|작성자 큰돌

#include<iostream>
using namespace std;
int n, m, a[100000], b, c;
int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		cin >> b;
		a[i] = a[i - 1] + b;
	}
	for (int i = 0; i < m; i++)
	{
		cin >> b >> c;
		if (b == 1)
			cout << a[c] << endl;
		else
			cout << a[c] - a[b-1] << endl;
	}
}