【Leetcode每日一题】前缀和（难度⭐）（25）

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")