[BOJ]11659-구간 합 구하기 4

11659

처음 시도했을 때 시간 초과, 2차원 벡터로 전체 합 저장하려고 보니 메모리 초과, 알고리즘 열어보니 누적 합이라고 나와서 적용했더니 틀렸습니다...

마지막엔 개행 문자를 안 넣어서 생긴 문제 ㅎㅎ

성공코드

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

int arr[100002];
long long sum[100002];

void fillIn(int size)
{
	for (int i = 1; i <= size; i++)
	{
		sum[i] = sum[i - 1] + arr[i];
	}
}

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

	int N, M;
	cin >> N >> M;

	for (int i = 1; i <= N; i++)
	{
		int tmp;
		cin >> tmp;

		arr[i] = tmp;
	}

	fillIn(N);

	for (int i = 0; i < M; i++)
	{
		int start, end;

		cin >> start >> end;
		
		long long res = sum[end] - sum[start-1];

		cout << res << '\n';
	}

	
}