何为前缀和算法？

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

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…+arSl-1 = a1+a2+a3+…+al-1

俩个相减

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

作用

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

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

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

#include<iostream>int main(){ int s[10] = {1,2,3,4,5,6,7,8,9,0};for(int i = 1; i <= n; i++){  s[i] = s[i-1] + a[i];}printf("%d",s[r] - s[l-1]);return 0;}

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

最后

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