蓝桥杯一维前缀和 | 算法基础

梦里梦外; 2024-04-20 07:37 66阅读 0赞

⭐**简单说两句**⭐

> **✨ 正在努力的小新~**  
> **? 超级爱分享，分享各种有趣干货！**  
> **?? 提供：模拟面试 | 简历诊断 | 独家简历模板**  
> **? 感谢关注，关注了你就是我的超级粉丝啦！**  
> **? 以下内容仅对你可见~**
> 
> **作者：****后端小知识**，**CSDN后端领域新星创作者 |阿里云专家博主**
> 
> **CSDN**个人主页：[后端小知识][Link 1]
> 
> ?**GZH**：`后端小知识`
> 
> ?欢迎关注?点赞?收藏⭐️留言?

--------------------

亲爱的友友们，大家元旦快乐吖????

祝各位友友们在2024年开开心心，顺顺利利，红红火火????

![image-20240101193509345][]

我们今天还是来讲解一个简单的算法吧，这个算法在比赛（蓝桥杯，ICPC，ACM）中用到的概率挺高的，经常用来优化时间复杂度，

这个算法的名字叫做 前缀和算法

### 概念 ###

我们先来了解一下一些概念性的东西

> 前缀和（Prefix Sum）是算法中的一种技巧，主要用于处理数组或序列的累积和问题。在计算机科学中，前缀和数组是一个一维数组，其中每个元素是原数组对应位置之前所有元素的和。换句话说，前缀和数组的第i个元素是原数组从第0个元素到第i-1个元素的和。

?例如，给定一个数组A = \[1, 2, 3, 4\]，其前缀和数组P = \[1, 3, 6, 10\]。这里，P\[0\] = A\[0\] = 1，P\[1\] = A\[0\] + A\[1\] = 1 + 2 = 3，P\[2\] = A\[0\] + A\[1\] + A\[2\] = 1 + 2 + 3 = 6，以此类推。

?前缀和的应用非常广泛，它可以用来解决许多问题，如：

1.  **区间和查询**：给定一个区间\[l, r\]，可以通过前缀和数组快速计算区间\[l, r\]内元素的和，即P\[r\] - P\[l-1\]。
2.  **更新操作**：如果需要在原数组的某个位置增加一个值，可以通过更新前缀和数组来反映这个变化，而不需要重新计算整个数组的前缀和。
3.  **差分数组**：前缀和数组可以用于构建差分数组，差分数组是前缀和数组的前缀和数组，可以用来解决一些需要计算相邻元素差的问题。
4.  **优化算法**：在动态规划、二分查找等算法中，前缀和可以用于优化时间复杂度，减少不必要的计算。

?前缀和的构建和查询操作的时间复杂度都是O(n)，其中n是数组的长度。在实际应用中，前缀和数组通常用于需要频繁查询区间和或进行区间更新的场景。

### 例子 ###

下面我们开始实践环节

我们来看一道Acwing上面的模板题：

?我也直接给家人们要来了（贴心吧❤️）：[前缀和][Link 2]

![image-20240101183422287][]

这题目意思还是很清晰吧

这个题我们肯定是不能直接双重循环去做的，肯定会TLE的，不信你可以试试?

这个题的优化做法就是用前缀和来做，是很明显的模板题啦?

我们直接上code?

### 代码 ###

> AC代码清单

#include<bits/stdc++.h>
    using namespace std;
    int n,m,l,r;
    int a[100010];
    int sum[100010];
    int main(){
        
        cin>>n>>m;
        for(int i=1;i<=n;i++){
        
            cin>>a[i];
            sum[i]=sum[i-1]+a[i];
        } 
        while(m--){
        
            cin>>l>>r;
            cout<<sum[r]-sum[l-1]<<"\n";
        }
        return 0;
    }

这个代码也是非常简单，大家如果?疑问❓的话，可以在评论区留言哟?

【都看到这了，点点赞点点关注呗，爱你们】??

![抽象工厂  引导关注][199c21e10d589f1889bfb9e864daecc6.png]

**✨ 正在努力的小新~**  
**? 超级爱分享，分享各种有趣干货！**  
**?? 提供：模拟面试 | 简历诊断 | 独家简历模板**  
**? 感谢关注，关注了你就是我的超级粉丝啦！**  
**? 以下内容仅对你可见~**

**作者：****后端小知识**，**CSDN后端领域新星创作者 | 阿里云专家博主**

**CSDN**个人主页：[后端小知识][Link 1]

?**GZH**：`后端小知识`

?欢迎关注?点赞?收藏⭐️留言?

[Link 1]: https://blog.csdn.net/m0_46833224
[image-20240101193509345]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/dcafa4bcdac7444fbf4f16a64810613a.png
[Link 2]: https://www.acwing.com/problem/content/description/797/
[image-20240101183422287]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/286932bef64f4a49b2506cff32a1627d.png
[199c21e10d589f1889bfb9e864daecc6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/eaca8cb54a684d5f8816370eeb1690df.png