基础算法——前缀和详解
【摘要】 秋名山码民的主页🎉欢迎关注🔎点赞👍收藏⭐️留言📝🙏作者水平很有限,如果发现错误,一定要及时告知作者 前言由于有些读者朋友私聊我,希望出几期基础算法的讲解,kmp,dp,哈希,搜索,贪心等对初学者还是不太友好,所以我打算更新几期基础算法合集,没办法谁让我宠粉丝呢?彦祖,热巴说你呢,快关注!目录大致如下:排序(十大排序)——已经讲过高精度算法从0->1入门双指针前缀和二分位运算区间合并...
秋名山码民的主页
🎉欢迎关注🔎点赞👍收藏⭐️留言📝
🙏作者水平很有限,如果发现错误,一定要及时告知作者
前言
由于有些读者朋友私聊我,希望出几期基础算法的讲解,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)
最后
看在博主这么努力,熬夜肝的情况下,给个免费的三连吧!
【声明】本内容来自华为云开发者社区博主,不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息,否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
作者其他文章
评论(0)