目录
1、前缀和2、前缀和算法有什么好处？3、二维前缀和4、差分5、一维差分6、二维差分
1、前缀和
前缀和是指某序列的前n项和，可以把它理解为数学上的数列的前n项和，而差分可以看成前缀和的逆运算。合理的使用前缀和与差分，可以将某些复杂的问题简单化。
 
加粗样式
 
2、前缀和算法有什么好处？
先来了解这样一个问题：
 
输入一个长度为n的整数序列。接下来再输入m个询问，每个询问输入一对l, r。对于每个询问，输出原序列中从第l个数到第r个数的和。
 
我们很容易想出暴力解法，遍历区间求和。
 
代码如下：
 
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
while(m–)
{
    int l,r;
    int sum=0;
    scanf("%d%d",&l,&r);
    for(int i=l;i<=r;i++)
    {
        sum+=a[i];
    }
    printf("%d\n",sum);
}
这样的时间复杂度为O(n*m)，如果n和m的数据量稍微大一点就有可能超时，而我们如果使用前缀和的方法来做的话就能够将时间复杂度降到O(n+m),大大提高了运算效率。
 
具体做法：
 
首先做一个预处理，定义一个sum[]数组，sum[i]代表a数组中前i个数的和。
 
求前缀和运算：
 
const int N=1e5+10;
int sum[N],a[N]; //sum[i]=a[1]+a[2]+a[3]…..a[i];
for(int i=1;i<=n;i++)
{
    sum[i]=sum[i-1]+a[i];   
}
然后查询操作：
 
 scanf("%d%d",&l,&r);
 printf("%d\n", sum[r]-sum[l-1]);
对于每次查询，只需执行sum[r]-sum[l-1] ，时间复杂度为O(1)
 
原理
 
sum[r] =a[1]+a[2]+a[3]+a[l-1]+a[l]+a[l+1]……a[r];
sum[l-1]=a[1]+a[2]+a[3]+a[l-1];
sum[r]-sum[l-1]=a[l]+a[l+1]+……+a[r];