前缀和与差分
本篇博客适合初学者阅读，如有不周之处，欢迎各位大佬指正！
-
0.背景
想象一下，你有一个数组（ 很长很长de那种 ）你需要求出给定一段区间的和，并有多次询问，作为初学者你是否要\(\boxed{for}\)循环把他们都加起来呢？
-
1.正文
前缀和
前缀和是一个数列A通过递推能够求出来的信息之一，顾名思义就是某个数前面所有单元数值之和。他的公式如下
\[S_i=\sum\limits_{j=1}^iA_j
\]
对于给定数列A，我们可以通过如下代码实现前缀和
for(rg int i=1;i<=n;i++){
S[i]=S[i-1]+A[i]
}
代码中的 \(S[i]=S[i-1]+A[i]\) 就是前缀和的递推式
一个问题：如果我们想要求一个区间$ [l,r]$的和，我们应该如何实现？
由于\(S\)代表数列\(A\)的前缀和，我们想要求一个闭区间的和只需要去掉\(l\)之前的所有部分就行了
\[ans=\sum\limits_{i=l}^rA_i=S_r-s_{l-1}
\]
所以我们就求出了\([l,r]\)的和
差分
对于一个给定数列\(A\)，它的差分数列\(C\)定义为
\[B_i=A_i-A_{i-1}\text{ } (2\leq i\leq n)
\]
差分可以看做前缀和的逆运算
你可以认为\(\boxed{\text{前缀和数列}}\)的\(\boxed{\text{差分数列}}\)就是\(\boxed{\text{原数列}}\)，\(\boxed{\text{差分数列}}\)的\(\boxed{\text{前缀和数列}}\)也是\(\boxed{\text{原数列}}\)
利用差分，我们可以区间多次以\(O(1)\)复杂度区间修改一个数组
实现方法：
我们将原数组想象为高度不同的一片高楼(如下图)
//未完待续