문제 출처

1. 문제설명

• 수 N개가 주어졌을 때, i~j번째 수까지 합을 구하라

2. 알고리즘 설계

• 누적합(prefix sum) 문제이다.
• 누적합 예시
  • 0, 1, 2, 3이 있다고 하자.
  • 1번째 값은 0이 된다.
  • 2번째 값은 1번째까지 누적된 값에서 2번째 값을 더한다.
  • 3번째 값은 2번째까지 누락된 값에서 3번째 값을 더한다.
• 누적합 로직
  • 배열의 인덱스는 1부터 시작하는 게 편하다.
  • prefix[i] = prefix[i-1] + arr[i]
• i부터 j번째 까지 구하는 방법
  • prefix[j]는 j까지의 누적합이다.
  • prefix[i-1]은 i의 이전 위치까지의 누적합이다.
  • prefix[i~j] = prefix[j] - prefix[i-1] 이라고 할 수 있다.

3. 전체 코드

#include <bits/stdc++.h>
using namespace std;

const int SZ = 100001;
int n, m, arr[SZ], prefix[SZ];
vector<int> ans;

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);

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

	while(m--) {
		int i, j;
		cin >> i >> j;
		cout << (prefix[j] - prefix[i-1]) << '\n';
	}
	
    return 0;
}