[백준][C++] 17390: 이건 꼭 풀어야 해!

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

 

정렬 후, 누적합(prefix sum)을 만들어준 뒤 배열 맨앞에 0을 추가해주면 B[R]-B[L-1]로 구간합을 빠르게 구할 수 있습니다.

세그먼트 트리도 되겠지만.. 굳이?

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


typedef long long ll;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
	
	int n, q;
	cin >> n >> q;
	vector<ll> v(n+1);
	for (int i=1; i<n+1; ++i)
		cin >> v[i];

	sort(v.begin(), v.end());

	for (int i=1; i<n+1; ++i)
		v[i] += v[i - 1];
	
	while (q--) {
		int l, r;
		cin >> l >> r;
		cout << v[r] - v[l-1] << '\n';
	}

	return 0;
}