【算法|前缀和系列No.1】牛客网 DP34 【模板】前缀和

Bertha 。 2024-04-27 06:36 110阅读 0赞

> 个人主页：[兜里有颗棉花糖][Link 1]  
> 欢迎 点赞? 收藏✨ 留言✉ 加关注?本文由 [兜里有颗棉花糖][Link 1] 原创  
> 收录于专栏【[手撕算法系列专栏][Link 2]】【[牛客网刷题][Link 3]】  
> ?本专栏旨在提高自己算法能力的同时，记录一下自己的学习过程，希望对大家有所帮助  
> ?希望我们一起努力、成长，共同进步。  
> ![在这里插入图片描述][503fbf94852e4752a15da4b418a9909c.png]

[点击直接跳转到该题目][Link 4]

#### 目录 ####

*  1️⃣题目描述
 *  2️⃣题目解析
 *  3️⃣解题代码

## 1️⃣题目描述 ##

**题目描述：**  
给定一个长度为n的数组a1,a2,…,an。  
接下来有q次查询, 每次查询有两个参数l, r。  
对于每个询问, 请输出al,al+1,…ar。

**输入描述：**  
第一行包含两个整数n和q。  
第二行包含n个整数, 表示a1,a2,…,an。  
接下来q行,每行包含两个整数l和r。

1≤n,q≤ 1 0 5 10^\{5\} 105  
\- 1 0 9 10^\{9\} 109 ≤ a\[i\] ≤  1 0 9 10^\{9\} 109  
1 ≤ l ≤ r ≤ n

**输出描述：**  
输出q行,每行代表一次查询的结果。

**示例：**

> 输出：  
> 3 2  
> 1 2 4  
> 1 2  
> 2 3

## 2️⃣题目解析 ##

前缀和的思想是通过提前计算和存储每个位置前的元素之和，以便在需要时能够快速获取。通过预先计算并存储前缀和，我们`可以在O(1)的时间复杂度内获得任意区间内元素的和，而不需要每次都重新计算。`**对于前缀和问题的话总共分为两步骤：①创建一个前缀和数组；②使用前缀和数组。**

**状态表示：**

*  `dp[i]`：**表示数组从\[1,i\]之间所有元素的和**。

**状态转移方程：**

*  `dp[i] = dp[i - 1] + arr[i]`

**关于本题目的时间复杂度如下：**

*  **时间复杂度：`O(q) + O(n)`。`O(q)`是用来查询q次询问。而`O(n)`用来创建前缀和数组。**

## 3️⃣解题代码 ##

#include<iostream>
    #include<vector>
    using namespace std;
    
    int main()
    {
        
        int n,q;
        cin >> n >> q;
        vector<long long> arr(n + 1),dp(n + 1);
        for(int i = 1;i <= n;i++)
            cin >> arr[i];
        
        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;
    }

**最后就是代码通过啦！！！**

![在这里插入图片描述][ab8e998a5c5240a6bd04c952d6747729.png]

[Link 1]: https://xiaofeizhu.blog.csdn.net/
[Link 2]: https://blog.csdn.net/m0_74352571/category_12364106.html
[Link 3]: https://blog.csdn.net/m0_74352571/category_12275139.html?spm=1001.2014.3001.5482
[503fbf94852e4752a15da4b418a9909c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/3f16e4b5449f4f09803695d8faa964fa.png
[Link 4]: https://www.nowcoder.com/practice/acead2f4c28c401889915da98ecdc6bf?tpId=230&tqId=2021480&ru=/exam/company&qru=/ta/dynamic-programming/question-ranking&sourceUrl=/exam/company
[ab8e998a5c5240a6bd04c952d6747729.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/face86b5613746e28abeb904a985c693.png