[BOJ] 11659_구간 합 구하기 4 with cpp

# 생각

단순히 a[i] 부터 a[j] 값을 계산해서 출력하게 되면

최대 N번의 수를 더해야 하고, 횟수도 M개가 들어와 시간 복잡도가 O(NM)이 된다

N × M의 크기가 100억이므로 이 방법으로는 문제를 해결할 수 없다

 

Prefix sum이라는 기법을 통해 해결할 수 있다

 

테이블을 정의해보자면

d[i] = a[1] + a[2] + ... + a[i]이고

d[i] = d[i-1] + a[i]가 된다

 

이 테이블을 이용하게 되면

a[i] 부터 a[j]까지의 합은

( a[1]부터 a[j] ) - ( a[1]부터 a[i-1] )로 볼 수 있기 때문에

d[j] - d[i-1]임을 이끌어 낼 수 있다

 

 

# 전체 코드

#include <bits/stdc++.h>
using namespace std;

int arr[111111], d[111111];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		cin >> arr[i];
		d[i] = d[i - 1] + arr[i];
	}
	while (m--)
	{
		int i, j;
		cin >> i >> j;
		cout << d[j] - d[i - 1] << '\n';
	}
}

 

---

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

11659번: 구간 합 구하기 4