[C++] Prefix sum(구간합) 알고리즘

Prefix sum(구간합)이란 ?

※ Prefix sum(구간합): 구간 합이란 크기가 N인 배열(A라고 가정)이 주어졌을 때, 같은 크기 N인 배열(주로 P)로 표현한다.  각각의 index 0 <= i < n 의 P[i]는 A[0] + A[1] + … + A[i - 1] + A[i]로 표현할 수 있다.

 

Input : arr[] = {1, 2, 3, 4, 5}

Output : Prefix_arr[] = {1, 3, 6, 10, 15} 

 

	
int A[100];		// 입력 받을 배열
int P[100];		// 구간 합을 구할 배열
    
int n;
scanf("%d", &n);
    
for (int i = 1; i <= n; i++) 
	scanf("%d", &A[i]);
        
// P[0]은 0으로 설정해주고 1부터 n까지는 합을 구해서 P 배열에 넣어준다
P[0] = 0;		

for (int i = 1; i <= n; i++)
	P[i] = P[i - 1] + A[i];

---

Prefix sum algorithm examples 

1) 백준 11659번 - 구간 합 구하기 4 

https://www.acmicpc.net/problem/11659

11659번: 구간 합 구하기 4

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>

using namespace std;

int A[100005];
int P[100005];

int main()
{
	int N, M, k;
	scanf("%d %d", &N, &M);	// N과 M 입력

	for (k = 1; k <= N; k++) {
		scanf("%d", &A[k]);		// 입력받은 정수를 A배열에 저장
	}
	
	P[0] = 0;
	for (k = 1; k <= N; k++) {
		P[k] = P[k - 1] + A[k];		// P배열에 prefix sum 저장
	}

	int i, j;
	for (k = 1; k <= M; k++) {
		scanf("%d %d", &i, &j);
		printf("%d\n", P[j] - P[i-1]);
	}

	return 0;
}

---

2) Codeforces 1003 C - Intense Heat

https://codeforces.com/problemset/problem/1003/C

Problem - 1003C - Codeforces

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>

using namespace std;

int A[5005];
int P[5005];

int main()
{
	int n, k, i, j;
	double ans;

	scanf("%d %d", &n, &k);

	for (int i = 1; i <= n; i++) {
		scanf("%d", &A[i]);
	}
	P[0] = 0;

	for (int i = 1; i <= n; i++) {
		P[i] = P[i - 1] + A[i];
	}

	ans = 0.0;

	for (int j = k; j <= n; j++) {
		for (int i = 1; i <= n-j+1; i++) {
			ans = max(ans, (double)(P[i + j - 1] - P[i - 1]) / (double)j);
		}
	}
	printf("%lf\n", ans);

	return 0;
}

---

3) Codeforces 466 C - Number of Ways

https://codeforces.com/problemset/problem/466/C

Problem - 466C - Codeforces

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>

using namespace std;

long long A[500005];
long long P[500005];

int main()
{
	long long num, total, total3, cnt, cnt1;
	scanf("%lld", &num);

	for (int i = 1; i <= num; i++) {
		scanf("%lld", &A[i]);
	}
	P[0] = 0;

	for (int i = 1; i <= num; i++) {
		P[i] = P[i - 1] + A[i];
	}
	total = P[num];
	if (total % 3 != 0) {
		cnt = 0;
	}
	else {
		total3 = total / 3;
		cnt = 0;
		cnt1 = 0;
		for (int i = 1; i < num; i++) {
			if (P[i] == total3 * 2) {
				cnt += cnt1;
			}
			if (P[i] == total3) {
				cnt1++;
			}
		}
	}

	printf("%lld\n", cnt);

	return 0;
}

---

4) Codeforces 1285 B - Just Eat It!

https://codeforces.com/problemset/problem/1285/B

Problem - 1285B - Codeforces

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <algorithm>

using namespace std;

long long A[100005];
long long P[100005];
long long M[100005];

int main()
{
	long long n, i, j, t, total, MN, ans;

	scanf("%lld", &t);
	while (t > 0) {

		scanf("%lld", &n);
		for (i = 1; i <= n; i++) {
			scanf("%lld", &A[i]);
		}
		P[0] = 0;

		for (i = 1; i <= n; i++) {
			P[i] = P[i - 1] + A[i];
		}
		total = P[n];
		ans = 1;
		MN = 0;
		for (i = 1; i <= n; i++) {
			M[i] = P[i] - MN;
			MN = min(MN, P[i]);
			if (M[i] >= total) ans = 0;
		}
		if (ans == 1) printf("YES\n");
		else printf("NO\n");

		t--;
	}

	return 0;
}