这是C++算法基础-基础算法专栏的第十一篇文章，专栏详情请见此处。
引入
我们用朴素做法求一维数组的区间和时，一般是从前向后循环累加，它的时间复杂度为，当求区间和的次数过多，则会有超时的可能，那有没有时间复杂度更低的做法呢？当然有，这就是前缀和做法，它求区间和的时间复杂度为
。
下面我们就来讲一维前缀和的实现。
定义
前缀和是一种重要的预处理方式，能大大降低查询的时间复杂度。
过程
表示
对于原数组，一维前缀和额外开辟了一个数组
，对于每个
，储存了
，也就是说，
。
赋值
赋值操作一般在输入数组时同时进行，我们可以容易得出其递推公式：
。
求区间和
当我们想得到数组区间
中的和，应该怎么去做呢？这里我们用图表加以理解，
表示当前位未计入总和，
表示当前位计入总和（后图同理）。
首先，图一展示了起始状态，然后，我们将计入总和（图二），也就是计算了
的和，但我们并不需要
之前的数计入总和，所以最后将
减去（图三）。
得出结论：。
代码
下面给出一维前缀和代码：
表示：s[i]=a[1]+a[2]+...+a[i]
赋值：s[i]=s[i-1]+a[i]
求和：a[l]+...a[r]=s[r]-s[l-1]上一篇-高精度除法的实现 C++算法基础专栏文章 下一篇-二维前缀和的实现
每周六更新一篇文章，内容一般是自己总结的经验或是在其他网站上整理的优质内容
点个赞，关注一下呗~
