[BOJ] 11659번 구간 합 구하기 4 (C++)

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

11659번: 구간 합 구하기 4

 

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	int n, m, num, x, y;
	cin >> n >> m;
	vector<int> v(n + 1);
	for(int i = 1; i <= n; i++){
		cin >> num;
		v[i] = v[i - 1] + num;
	}
	for(int i = 0; i < m; i++){
		cin >> x >> y;
		cout << v[y] - v[x - 1] << '\n';
	}
	return 0;
}

누적합을 미리 구해놓고 구간이 주어지면 이 누적합을 통해서 구한다. 

 

벡터 v에는 주어진 배열의 첫 번째 원소부터 현재 원소까지의 합을 저장한다.

x번부터 y번 index까지의 값을 구하라고 한다면 v[y] - v[x - 1]을 통해서 구할 수 있다.