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

1. 题目解析

题index.php/tags-41973.html" >���链接：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 #include using namespace std;int main() {    int n, q;    cin >> n >> q;    vector arr(n + 1);    for(int i = 1; i > arr[i];        vector dp(n + 1);    for(int i = 1; i > l >> r;        cout