백준 17390 이건 꼭 풀어야 해!

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

숭고한 공식 풀이는 여기서 보실 수 있습니다.

대표적인 prefix sum 문제입니다. pre[x]=(arr[1]-arr[x]까지의 합)을 저장하는 배열을 하나 만들고, l부터 r까지 구간의 합을 물어본다면 pre[r]-pre[l-1]을 통하여 쿼리당 O(1)의 시간복잡도로 답을 구할 수 있습니다.

정렬은 편하게 STL을 사용합시다.ㅎㅎ

#include<bits/stdc++.h>
using namespace std;
const int SZ=300005;
int arr[SZ];
int pre[SZ];
int main(void){
	ios::sync_with_stdio(false); cin.tie(NULL);
	int n,q; cin>>n>>q;
	for(int i=1;i<=n;i++) cin>>arr[i];
	sort(arr+1,arr+n+1);
	for(int i=1;i<=n;i++){
		pre[i]=pre[i-1]+arr[i];
	}
	while(q--){
		int l,r; cin>>l>>r;
		cout<<pre[r]-pre[l-1]<<'\n';
	}
	return 0;
}