前缀和 和差分

前缀和，又称 和数组，用于求解获取某一部分连续区间的问题。

算法实现：定义一个和数组d,接着输入过后，用和数组中的第i个元素表示前i个数的和，递推式：d[i]=d[i-1]+a[i]，想要获取其中从x 到y的连续元素和， 只需要使用o(1)公式d[y+1]-d[x]即可。

算法原理：求和时 使用了简单的容斥原理，如下图所示                                                                                                                       

 算法比较：前缀和：o(n)，预处理加调用，系数=2   暴力算法：o(nm)，其中m是区间长度

原因：牺牲空间（多开了和数组），节省时间，简称：预处理干的多

----------------------------------------------------------------------------分割线-------------------------------------------------------------------------------

差分，又称差分数组，用于 对某一段连续区间中所有的元素进行批量处理，

算法实现，首先填满差分数组，使用递推式：d[i]=a[i]-a[i-1],接着对区间[x,y] 进行批量处理：d[x]-=do,d[y+1]+=do,用于对[x,y]进行-do操作，最后对差分数组进行前缀和

算法原理：我们称接受-do的所有元素拥有基因，并且如果后面一个元素也拥有基因， 就称之为遗传。我们 首先授予d[x]基因，那么 在前缀和的时候，基因就会 跟着前缀和向后遗传。为了让基因 停歇在d[y]处，我们就在d[y]处将do加上，让基因停止遗传。

算法比较：差分：o(n),预处理加调用，系数=2, 暴力算法：o(nm)，m是最大区间长度

原因：和前缀和一样，我们会发现，差分就是和数组的“逆运算”

最后附上ppt:

  题目多得很，自己搜一搜。

基本代码根据叙述自己写一写，如果写的不容易懂，可以结合大佬们的博客一起服用。