[Algorithm] 누적합(Prefix sum)을 이용한 구간합 구하기

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

11659번: 구간 합 구하기 4

 

✅ 누적합이란?

x0, x1... xn까지 수가 있을 때 y0 = x0, y1 = x0 + x1, yn = x0 + x1 +... + xn처럼 해당 n까지의 합을 의미한다.

y0 = x0
y1 = x0 + x1
y2 = x0 + x1 + x2
...
yN = x0 + x1 + ... + xN

 

✅  누적합의 성질

i부터 j의 합을 구하려면 누적합 j에서 누적합 i - 1을 빼주면 된다. 

S[j] - S[i-1] = a[i] + a[i+1] + ... + a[j-1] + a[j]

 

누적합 알고리즘 O(n)

 

매번 요청이 들어올 때마다 합을 구하는 방법O(n^2)도 있지만,

누적합을 이용해 미리 요청이 들어올 때마다 구해놓은 preSum 배열을 이용해 값을 바로 반환한다.

 

즉, `5 4 3 2 1`로 예제가 주어진다면 다음과 같이 값이 할당될 것이다.

preSum[1] = 5

preSum[2] = 9

preSum[3] = 12

preSum[4] = 14

preSum[5] = 1

 

ex) 2에서 4 부분합을 구하고 싶다면?

preSum[4] - preSum[2 - 1] = 9 

#include <algorithm>
#include <iostream>
using namespace std;

int N, M, num;
int x, y, preSum[100001];

int main() {
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		cin >> num;
		preSum[i] = preSum[i - 1] + num;
	}

	for(int i = 0; i < M; i++){
		cin >> x >> y;

		if (x == 0) {
			cout << preSum[y] << "\n";
		}
		else {
			cout << preSum[y] - preSum[x - 1] << "\n";
		}
	}
}