[Algorithm] 누적합(Prefix Sum)

1. 누적합

누적합은 앞에서부터 차례대로 누적된 합을 구하고 이를 이용해 구간 합을 구할 수 있다.

2. 문제

크기가 N인 정수 배열 arr가 존재할 때 다음과 같은 연산을 M번 수행해야하는 문제가 존재한다.

 - 구간 l, r(l <= r)이 주어졌을 때, arr[l] + arr[l + 1] + ... + arr[r]을 구해 출력

l부터 r까지를 구하기 위해, 반복문을 통해 단순히 구하게 된다면 시간 복잡도는 O(NM)이 나오게 된다.

 

여기서, 누적합 아이디어로 변경해보자.

sum[i] = arr[1] +... + arr[i], sum[0] = 0으로 정의하고, l부터 r까지의 합은 sum[r] - sum[l - 1]과 동일하다.

sum[r] = arr[1] + ... + arr[r], sum[l - 1] = arr[1] + ... + arr[l-1] 으로 정의되므로, 따라서 sum[r] - sum[l - 1]은 arr[l] + arr[l + 1] + ... + arr[r]으로 나오게 된다.

구간합을 구하기 위해 뺄셈 연산 한번만 진행하면 되므로 시간 복잡도는 O(1)이다. 따라서 M번 수행하면 총 시간 복잡도는 O(M)이 나오게 된다. 

3. 예시

백준의 구간 합 구하기4 문제를 통해 예를 들어본다. 

수 N개가 주어졌을 때 i ~ j수까지의 합을 구하는 프로그램을 작성하면 되므로, 위에서 사용한 내용을 토대로 코드를 구현하면 아래와 같다. 

for (int i = 1; i < numbers.size(); i++) {
	numbers[i] = numbers[i - 1] + numbers[i]; // 누적합을 구하는 공식
}

while (M--) {
	cin >> start >> end; // start ~ end의 구간합
	cout << numbers[end] - numbers[start - 1] << "\n"; 
    // 이미 누적합으로 저장되어있으므로 뺄셈만 해주면 됨
}

---

참고 문헌

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