1. 題目解析

題目鏈接：DP34 【模板】前綴和

這個問題的理解其實相當簡單，只需看一下示例，基本就能明白其含義了。

核心在于計算題目所給區間數組元素和返回即可。

2. 算法原理

• 為了提高計算效率，我們可以預先計算出一個「前綴和」數組。這個數組 dp[i] 的含義是：數組中從第 1 個元素到第 i 個元素（包含兩端）的和。
• 因此，dp[i - 1] 就代表了從第 1 個元素到第 i - 1 個元素的和。通過這樣一個數組，我們可以方便地通過遞推公式 dp[i] = dp[i - 1] + arr[i] 來計算得到任意位置的前綴和。
• 一旦我們有了這個前綴和數組，計算任意區間 [l, r] 內所有元素的和就變得非常簡單且快速。具體來說，區間 [l, r] 內所有元素的和可以通過 dp[r] - dp[l - 1] 來快速得到。
• 這是因為 dp[r] 包含了從第 1 個元素到第 r 個元素的和，而 dp[l - 1] 包含了從第 1 個元素到第 l - 1 個元素的和，兩者相減即得區間 [l, r] 的元素和。

3. 代碼編寫?

#include <iostream>
#include <vector>
using namespace std;int main() 
{int n, q;cin >> n >> q;vector<int> arr(n + 1);for(int i = 1; i <= n; i++)cin >> arr[i];vector<long long> dp(n + 1);for(int i = 1; i <= n; i++)dp[i] = dp[i - 1] + arr[i];while(q--){int l, r;cin >> l >> r;cout << dp[r] - dp[l - 1] << endl;} return 0;
}
// 64 位輸出請用 printf("%lld")

The Last

嗯，就是這樣啦，文章到這里就結束啦，真心感謝你花時間來讀。

覺得有點收獲的話，不妨給我點個贊吧！

如果發現文章有啥漏洞或錯誤的地方，歡迎私信我或者在評論里提醒一聲~?

?