누적합(Prefix Sum) 알고리즘

 누적합 알고리즘(Prefix Sum Algorithm)은 배열이나 리스트같은 데이터에서 연속된 부분의 합을 빠르게 계산하기 위한 알고리즘이다. 이 알고리즘은 주어진 배열의 각 요소에 대해 이전 요소까지의 누적합을 미리 계산해 두고, 이를 활용하여 특정 구간의 합을 효율적으로 구하는 데 사용된다. 누적합과 관련된 여러 문제가 있지만 먼저 가장 기본적인 누적합의 형태에대해 알아보자.

---

누적합 알고리즘의 기본 개념

• 누적합 배열(Sum Array):
  주어진 배열 A의 누적합 배열 Sum을 만든다. S[i]는 A 배열의 0번째부터 i번째 요소까지의 합을 뜻한다. 즉, S[i] = A[0] + A[1] + ... + A[i]
• 구간 합 계산:
  배열 A의 구간 [i, j] (i <= j)에 대한 합을 구하려면, 누적합 배열 S를 사용하여 S[j] - S[i-1]을 계산하면 된다. 여기서 S[j]는 0부터 j까지의 합을, S[i-1]은 0부터 i-1까지의 합을 나타내므로, 이를 빼면 [i, j] 구간의 합이 된다.

---

시간 복잡도

 

• 전처리: 누적합 배열을 생성하는 데 O(n)이 걸린다.
• 구간 합 계산: 각 구간 합 계산은 O(1)이 걸린다.

---

-> 누적합의 기본 문제를 통해 더 자세히 알아보자

백준 구간 합 구하기 4(11659)문제를 살펴보자

 

이 문제는 주어진 배열의 누적합 쿼리를 처리하는 문제이다.

입출력 예제를 통해 알아보자.

arr[]

5

4

3

2

1

arr배열이 위와 같이 존재할때, 이를통한 sum배열의 전처리가 필요하다.

sum[]

5

9

12

14

15

sum[i] = sum[i - 1] + arr[i]를 통해 O(n)안에 sum배열을 모두 채울 수 있다.

이 sum배열을 통해서주어진 구간의 합을 구하면 된다.

구간 i~j사이의 합은 sum[j] - sum[i - 1]을 통해 구할 수 있다.

만약 1 ~ 3까지의 구간의 합을 구한다면 12(sum[3]) - 0(sum[0]) = 12로 구할 수 있다.

다른 데이터들도 위와같은 방법으로 구할 수 있다.

---

소스코드

#include <stdio.h>

int n, t;
int sum[100010];

int main()
{
	int i, j;
	scanf("%d %d", &n, &t);
	for (i = 1; i <= n; i++) {
		int x;
		scanf("%d", &x);
		sum[i] = sum[i - 1] + x;
	}
	while (t--) {
		int x, y;
		scanf("%d %d", &x, &y);
		printf("%d\n", sum[y] - sum[x - 1]);
	}
	return 0;
}