백준 11659번 : 구간 합 구하기 4 [C++]

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

11659번: 구간 합 구하기 4

소스 코드 :

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int N, M;
	int sum = 0;
	vector<int> v(100001);
	v[0] = 0;
	cin >> N >> M;

	for (int i = 1; i <= N; i++)
	{
		int element;
		cin >> element;
		sum += element;
		v[i] = sum;
	}

	while (M != 0)
	{
		int start, end;
		cin >> start >> end;

		cout << v[end] - v[start-1] << '\n';
		M--;
	}
}

마무리 : 이 문제를 처음 풀었을 때는 i번째부터 j번째까지 직접 더하는 식으로 구했는데 시간 초과가 걸렸다. 그래서 어떻게 하면 시간을 줄일 수 있을까 생각을 하였는데 이럴 때는 누적합으로 구하면 시간을 줄여서 시간 초과가 걸리지 않는다.