前綴和，就是通過一種方法來求出數組中某個連續區間的元素的和的辦法。我們通常先預處理出來一個前綴和數組，然后把數組中進行元素填充后再進行后續使用。

我們通過一道模板題或許能更加理解其意思。?

現在的問題就是：如果我們用暴力枚舉來記錄每次l與r之間的和，那么肯定是會超時的（時間復雜度O（N*q）），我們要另辟蹊徑。我們用一下上面的前綴和算法。

假設我們原有的數組為arr，現在我們要另創建一個數組dp。這個dp數組的每一個元素dp[i]記錄著arr[i]及之前的元素之和。

注意，我們這里的arr和dp中的i都是以1開始記錄而不是0，稍后我們解釋一下原因，我們先把arr[0]和dp[0]都看成0。dp中的元素計算公式為：
dp[i]=dp[i-1]+arr[i];

利用這個公式，我們也可以把dp數組進行初始化。接下來就是如何使用，

假設我們要求l-r的和，只需要用dp[r]-dp[l-1]即可。

通過這個公式我們就可以說明為什么下標需要從1開始了，如果l為0，也就是想求從最左到r，那么公式里就是dp[r]-dp[-1]。越界是萬萬不可的。所以我們要把arr和dp的0位置空出來并標記為0即可（0并不影響求和）。這種方法我們就成功把時間復雜度變成了o(q)+o(n)。

我們把題解寫一下，（代碼過程基本就是模板）

#include <iostream>
#include <vector>using namespace std;int main()
{int n,q;cin >>n>>q;//創建一個n+1個數大小的vector （0-n）vector <int>arr (n+1);for(int i=1;i<n+1;i++) cin>>arr[i];//創建前綴和數組vector<long long> dp(n+1);for(int i=1;i<n+1;i++) dp[i]=dp[i-1]+arr[i];//使用前綴和int l=0,r=0;while(q--){cin>>l>>r;cout<<dp[r]-dp[l-1]<<endl;}return 0;
}