- ์ด ๊ธ์ c++๋ก ํ์ด๋ฅผ ์์ฑํ์์ต๋๋ค.
๋ฌธ์
์์
ํ์ด
- Prefix sum ๊ตฌํ๊ธฐ ๋ฌธ์ ์
๋๋ค.
- DP๋ฅผ ์ฌ์ฉํ๋ฉด ์๊ฐ๋ณต์ก๋ O(N)์ ๊ตฌํ ์ ์์ต๋๋ค.
- D[i] = D[i-1] + D[i-2] +... +D[1]
#include<iostream>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int arr[100000]={0};
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>arr[i];
arr[i]+=arr[i-1];
}
for(int i=0;i<m;i++){
int a,b;
cin>>a>>b;
cout<<arr[b]-arr[a-1]<<"\n";
}
}
- ์ถ๊ฐ๋ก ๊ถ๊ธํ ์ ์ด๋ ์์ ํ ๋ถ๋ถ ์์ผ๋ฉด ๋๊ธ๋ก ๋จ๊ฒจ์ฃผ์ธ์.