> Markdown代码2616字，渲染出实际1934字
前言
前缀和和差分是优化的常见手段。
本篇很水
前缀和
假设有一个数组AAA,现在要对AlA_lAl 到ArA_rAr 进行求和。
假设l=2,r=4l=2,r=4l=2,r=4,那么求和的操作：
首先新建两个变量：ans=0ans=0ans=0用于记录和，i=li=li=l用于求和操作。
ans=0,i=2ans=0,i=2ans=0,i=2
接下来将ansansans加上iii指向的值，并将i右移：
ans=2,i=3ans=2,i=3ans=2,i=3
继续累加ansansans并右移iii：
ans=5,i=4ans=5,i=4ans=5,i=4
iii到达rrr，累加ansansans并结束。
最终答案：ans=8ans=8ans=8
可以发现，这里的方法如果用代码实现，时间复杂度很高(O(r−l+1)O(r-l+1)O(r−l+1))，如果题目给到的数据大一点就会爆TLE\color{blue}TLETLE。
这个时候，就可以使用前缀和来优化代码，实现O(1)O(1)O(1)的时间复杂度。
新建一个数组SSS，SiS_iSi 表示AAA数组前iii项的值，即Si=A1+A2+⋯+Ai−1+AiS_i=A_1+A_2+\cdots+A_{i-1}+A_iSi =A1 +A2 +⋯+Ai−1 +Ai 。
S1=A1S_1=A_1S1 =A1
S2=A1+A2S_2=A_1+A_2S2 =A1 +A2
S3=A1+A2+A3S_3=A_1+A_2+A_3S3 =A1 +A2 +A3
S4=A1+A2+A3+A4S_4=A_1+A_2+A_3+A_4S4 =A1 +A2 +A3 +A4
S5=A1+A2+A3+A4+A5S_5=A_1+A_2+A_3+A_4+A_5S5 =A1 +A2 +A3 +A4 +A5
S6=A1+A2+A3+A4+A5+A6S_6=A_1+A_2+A_3+A_4+A_5+A_6S6 =A1 +A2 +A3 +A4 +A5 +A6
依旧是l=2,r=4l=2,r=4l=2,r=4求区间和：
这段区间的区间和是A2+A3+A4A_2+A_3+A_4A2 +A3 +A4 ，刚好等于S4−S1S_4-S_1S4 −S1 。
验证答案：S4−S1=9−1=8S_4-S_1=9-1=8S4 −S1 =9−1=8。答案正确！
也就是说，lll到rrr的区间和为Sr−Sl−1S_r-S_{l-1}Sr −Sl−1 。
那么如何在程序中快速生成前缀和数组呢？
我们可以注意到，SiS_iSi 只比Si−1S_{i-1}Si−1 多一个AiA_iAi ，如：
S3=A1+A2+A3S_3=A_1+A_2+A_3S3 =A1 +A2 +A3
S4=A1+A2+A3⏟S3+A4=S3+A4S_4=\underbrace{A_1+A_2+A_3}_{S_3}+A_4=S_3+A_4S4 =S3 A1 +A2 +A3 +A4 =S3 +A4
得出：Si=Si−1+AiS_i=S_{i-1}+A_iSi =Si−1 +Ai 。
程序实现
> 一个小特性：当i=1,程序内s[1]=s[0]+a[1],如果s为全局变量则s[0]等于0,s[1]直接等于a[1]。
差分
有一个数组AAA，现在要将数组中从lll到rrr区间的数全部加上ttt。
常规暴力实现：假设l=2,r=4,t=3l=2,r=4,t=3l=2,r=4,t=3，定义一个i=li=li=l。
将iii指向的数加上ttt，并将i+1i+1i+1：
继续操作：
iii到达rrr，最后一次操作iii指向的元素加上ttt，循环结束。
结束后的数组AAA：
这个方法的时间复杂度依然是O(r−l+1)O(r-l+1)O(r−l+1)。
要优化这里的代码，可以使用差分。
> 差分适用于有多次区间加减的题目，单次加减甚至会负优化(O(t(r−l+1))O(t(r-l+1))O(t(r−l+1))到O(tn)O(tn)O(tn))
增加差分数组DDD:
其中Di=Ai−Ai−1D_i=A_i-A_{i-1}Di =Ai −Ai−1 。
对于每次操作，将DlD_lDl 加上ttt，Dr+1D_{r+1}Dr+1 减去ttt.
解释：增大AlA_lAl 的值会增大Di(Ai)−Ai−1D_i(A_i)-A_{i-1}Di (Ai )−Ai−1 的值，而lll到rrr区间内的值由于一起加减，差分数组不变。
增大ArA_rAr 的值会减小Dr+1(Ar+1−Ar)D_{r+1}(A_{r+1}-A_r)Dr+1 (Ar+1 −Ar )的值，所以减去ttt。
> 此处假设DiD_iDi 只有正数。
最后，给DDD数组做一个前缀和得到原数组AAA。
解释：Di=Ai−Ai−1,Ai=Di+Ai−1D_i=A_i-A_{i-1},A_i=D_i+A_{i-1}Di =Ai −Ai−1 ,Ai =Di +Ai−1 。
代码实现：
> 因为差分只需要AiA_iAi 和Ai−1A_{i-1}Ai−1 来构造，因此不创建AAA，只用变量存储Ai−1A_{i-1}Ai−1 即可。
结尾
到这里就结束了前缀和和差分的解释和一维实现。二维正在赶工······
