前缀和

给定一个数列A,它的前缀和S是通过递推能求出的信息之一:
$$
S[i]=\sum_{j=1}^iA[j]
$$
某个区间的部分和可以写成前缀和相减:
$$
sum(l, r)=\sum_{i=l}^rA[i]=S[r]-S[l-1]
$$

差分

对于给定数列A,差分数列B的定义:
$$
B[1]=A[1],B[i]=A[i]-Ai-1
$$
前缀和与差分是一对互逆运算,差分的前缀和是原数列。