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

 

1) 문제설명

백준 Online Judge 11659번 구간 합 구하기 4

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

11659번: 구간 합 구하기 4

 

2) 아이디어

for문을 2번 사용하여 구간의 합을 구 할 경우 O(N^2)의 시간이 걸리기 때문에 O(N+M)의 시간 안에 문제를 해결해야 한다.

구간의 합을 배열로 설정한 후 미리 구하여 b번째의 합에서 a-1번째의 합까지를 빼면 구간 a~b까지의 구간의 합을 구할 수 있다.

 

3) 코드

#include<iostream>
#include<queue>
#include<deque>
#include<string.h>
#include<math.h>
#include<cmath>
#include<stack>
#include<algorithm>

using namespace std;
int arr[100001];
int sum[100001];
int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		scanf("%d", &arr[i]);
	}
	for (int i = 1; i <= n; i++) {
		sum[i] = sum[i - 1] + arr[i];
	}
	for (int i = 0; i < m; i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		printf("%d\n", sum[b] - sum[a - 1]);
	}
}