題目連結: https://zerojudge.tw/ShowProblem?problemid=a693
# 解題思路
運用前綴和的辦法解決這問題吧
一維陣列變數 A [10001], S [10001]
輸入資料 A [] 的同時建立累加表 S []
S [i] = A0+A1+...+Ai (前面 i 項的總和)
之後，從 a 項到 b 項的總和 = S [b] - S [a-1]
(這是 DP 的觀念之一喔～)
# 程式碼
#include<iostream> | |
using namespace std; | |
int main(){ | |
int n,m,hun[100001],S[100001]={0}; | |
while(cin>>n>>m){ | |
for(int i=1;i<=n;i++){ | |
cin>>hun[i]; | |
S[i]=S[i-1]+hun[i]; | |
} | |
for(int i=0;i<m;i++){ | |
int l,r,sum; | |
cin>>l>>r; | |
sum=S[r]-S[l-1]; | |
cout<<sum<<endl; | |
} | |
} | |
} |
