11659번 : 구간 합 구하기 4

문제는 다음과 같습니다.

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

11659번: 구간 합 구하기 4

 

풀이 코드는 다음과 같습니다.

 

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	vector<long> v(n + 1);
	v[0] = 0;
	for (int i{1}; i <= n; i++) {
		long num;
		cin >> num;
		v[i] = v[i - 1] + num;
	}
	for (int i{1}; i < m; i++) {
		int s, e;
		cin >> s >> e;
		cout << v[e] - v[s - 1]<<'\n';
	}

	return 0;
}

정해진 구간을 for문 사용하여 구간합을 구하게 되면 시간초과되므로, vector에 넣을 때부터 누적합으로 계산된 값을 입력합니다.

1번부터 시작하기 때문에 0번째 원소에는 0을 먼저 입력해야 한다는 점을 주의해야합니다.