基础算法——前缀和详解

秋名山码民的主页 🎉欢迎关注🔎点赞👍收藏⭐️留言📝 🙏作者水平很有限，如果发现错误，一定要及时告知作者

前言

由于有些读者朋友私聊我，希望出几期基础算法的讲解，kmp，dp，哈希，搜索，贪心等对初学者还是不太友好，所以我打算更新几期基础算法合集，没办法谁让我宠粉丝呢？彦祖，热巴说你呢，快关注！

目录大致如下：

排序（十大排序）——已经讲过 高精度算法 从0->1入门双指针 前缀和 二分 位运算 区间合并

何为前缀和算法？

前缀和算法，属于基础算法，一般来说没有固定的模板，但是其思路值得借鉴，我们来看一个案例就懂了 一维前缀和最基本的用法

Si = a1+a2+a3+…+ai

如何求Si？

传统思路： 暴力枚举，代码如下

for(int i = 1; i <= n; i++){
	//直接累加
	s+=a[i];
	//自己设置退出条件
	
}

但是我们不满足于当前的时间复杂度O（n）想快一点，随便求一个区间前缀和，假设这个区间就为S[ l,r ] 这时就要请出我们高中所学的等差数列，像这样：

Sr = a1+a2+a3+…+al-1+al…+ar Sl-1 = a1+a2+a3+…+al-1

俩个相减

在这里插入图片描述

上图不难看出所得就是S[ l,r ]的区间和

作用

那么大家知道了什么是前缀和，一个东西的存在必然是有他的作用的，不然学他干嘛？

在这里插入图片描述

作用： 快速求一段和，上面暴力算法时间复杂度为O（n）,而现在的时间复杂度可降为O（1）

具体实现： 求s[ l, r ]的区间和

for(int i = 1; i <= n; i++){
	s[i] = s[i-1] + a[i];
}
printf("%d",s[r] - s[l-1]);

值得注意的一点是，我们一般将S[0] = 0,原因如下： 假设我们需要计算S【1，10】，那么S10 - S0可以直接得出，Sr - S（l-1）

最后

看在博主这么努力，熬夜肝的情况下，给个免费的三连吧！