누적합 (Prefix Sum)

1. 누적합이란?

배열에서 특정 구간의 합을 구해야할 때 사용되는 개념으로, 

배열 맨 앞에서부터 차례대로 값의 합을 누적하여 저장해놓고, 이를 이용해서 구간의 합을 구할 수 있다.

 

2. 누적합을 사용하는 경우 ( = Why? 왜 사용할까?)

배열에서 특정 구간의 합을 구할 때,

반복문을 통해 이를 구하면 시간 복잡도 문제가 생긴다.

 

예를 들어, 크기가 N인 배열 A의 인덱스 a부터 b까지의 합을 구해야한다면(a ≤ b), 다음과 같이 구할 수 있다.

• A[a] + A[a + 1] + ··· + A[b - 1] + A[b] 값

int sum = 0;

for (int i=a; i<=b; i++) {
	sum += A[i];
}

이 때의 시간 복잡도는 O(N)이다.

 

하지만, 반복문을 이용한 코드를 누적합 방식으로 바꾸면, 배열 원소의 특정 구간의 합을 O(1)의 시간 복잡도로 구할 수 있다.

 

먼저, 배열의 맨 앞에서부터 해당 위치까지의 누적합을 저장해놓는 배열 S[i]를 만든다.

즉, S[b] = A[0] + A[1] + ··· + A[b - 1] + A[b] 이고,

S[a] = A[0] + A[1] + ··· + A[a - 1] + A[a] 이다.

 

따라서,A[a]부터 A[b]까지의 구간합은 S[b] - S[a-1]로 구할 수 있다.

맨 처음에 누적합을 저장하는 배열 S를 만드는데 O(N)의 시간이 걸리며,

구간합을 구하는데는 뺄셈 연산 한번만 필요하기 때문에 O(1)의 시간이 걸린다.

 

3. 문제로 구현 방법 익히기

대표적인 문제를 통해 누적합 구현 방법을 알아보자.

문제

11659번: 구간 합 구하기 4

 

 

풀이

#include <iostream>
using namespace std;

int n, m;
int sum[100001]; // 누적합 값을 저장해놓는 배열

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  cin >> n >> m;
  
  // 누적합 배열 만들기
  for (int i=1; i<=n; i++) {
    int num;
    cin >> num;
    sum[i] = sum[i-1] + num;
  }

  for (int i=0; i<m; i++) {
    int start, end;
    cin >> start >> end; // 구간의 시작과 끝
    cout << sum[end] - sum[start - 1]<< '\n';
  }

  return 0;
}

 

4. 참고 자료

https://book.acmicpc.net/algorithm/prefix-sum

누적 합