前缀和+差分梳理&模板

简而言之，如果说连续函数有微积分，那么离散数列就有差分和前缀和

两者相互依存，也是彼此的逆运算

前缀和的实现方式很简单，只要每次新录入一个数就加上那个数就可以了

int a[N];
int prefix[N] = {0};
for(int i=1;i<=N;i++){
    cin >> a[i];
    prefix[i] = prefix[i-1]+a[i];
}

差分类似，只要每次新录入一个数就减去前面的数就好了

int a[N];
int diff[N] = {0};
for(int i=1;i<=N;i++){
    cin >> a[i];
    diff[i] = a[i]-a[i-1];
}

两者是把众人从O(n)区间查询和修改的苦海中救出来的良药

换句话说就是一系列

的题目的罪魁祸首，线段树，树状数组，可持久化线段树的下位替代

以下为主要用法

1.区间求和

前缀和数组的第i个位置，存储的是索引从0到i的所有元素之和，第j个位置存储的是从0到j的所有元素之和

那假设，你拿前缀和数组的第i个位置去减第j-1个位置，你是不是就可以得到第j到第i个元素的和？

只需要在输入输出的时候完成一步预处理，你就可以把后面所有的区间求和问题统统降到O(1)

纯粹的数值纯粹的强大

2.区间加

考虑，差分可以理解为数列在某一点的微分，如果你把这一段整体抬升多少，其实并不会改变区间中段的差分大小

你改变的无非就是头尾的差分而已

考虑如果你要区间加C，那你头部的差分也要加C

而由于前一个元素增加了C，尾部的差分需要减C

你只需要O(2)的操作你就可以等效改变一整个区间的值

纯粹的数值纯粹的强大

进一步拓展，还有二维的前缀和，以及二维的差分

二维前缀和顾名思义就是一个数组中的矩形中的所有值的和，二维差分略难感性理解，但的确也是前缀和的逆运算

如果你想要知道一个点的前缀和，应该如何递推？可以参考(a+b)^2的推法：

对于a[x][y]的前缀和pre[x][y]，其等于a[x][y]+pre[x][y-1]+pre[x-1][y]-pre[x-1][y-1]

你在求中间两个矩形的前缀和的时候，会不可避免地导致其中有一部分被计算两次，因此最后的减法是拿来去重用的

随后，只要取它的，呃，逆映射/反函数之类的东西你就可以得到a[x][y]的差分：

diff[x][y] = a[x][y]-a[x-1][y]-a[x][y-1]+a[x][y]

当然，差分和前缀和由于两者性质相悖，不能合二为一，如果你想合二为一，你可以去学树状数组和线段树