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

 

알고리즘 분류: 누적 합

문제 링크: https://www.acmicpc.net/problem/11659

11659번: 구간 합 구하기 4

 

 

 

 

【 풀이 】

 

• 1~4: (1~4)
• 2~5: (1~5) - (1~1)
• 3~6: (1~6) - (1~2)

즉 1~1, 1~2, 1~3, 1~4... 1~end까지의 구간합들을 sum이라는 배열에 따로 저장한다.

그리고 sum[end] - sum[start-1] 을 출력해 주면 끝.

만약 다음에 입력받는 end 변수가 전의 변수보다 더 크다면

또 새로운 end 까지의 구간합을 저장하면 된다.

 

 

 

【 코드 】

 

#include<iostream>
using namespace std;

int arr[100001];
int sum[100001];
int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int start, end, temp = 1, n, m;
	cin >> n >> m;

	for (int i = 1; i <= n; i++)
		cin >> arr[i];

	for (int i = 1; i <= m; i++)
	{
		cin >> start >> end;
		if (end < temp)
			cout << sum[end] - sum[start - 1] << '\n';
		else
		{
			for (int i = temp; i <= end; i++)
				sum[i] = sum[i - 1] + arr[i];
			cout << sum[end] - sum[start - 1] << '\n';
			temp = end;
		}
	}
	return 0;
}