写在最前面：

此系列中的所有模板全为大佬所写，我只是一个搬运工（？）。

记录：

前缀和：

前缀和，即为数组前n项的和。s[n]=a[1]+a[2]+......+a[n];多数被用来计算前面的和和下一个数字做比较。需要注意的是，在计算前缀和的时候，很有可能会数据越界，即使数组内的数字不会越界，相加的和也很有可能越界。在计算出所有数字的前缀和之后，可以计算[l,r]长度的和，即为s[r]-s[l-1]；
在计算前缀和的时候，为了避免数组越界，一般都从1开始计数。s[0]=a[0]=0；
计算前缀和的时候，可以利用递归减少循环次数，从而更快的计算前缀和。即s[i]=s[i-1]+a[i]；

下面是模板：

#include <iostream>
#include<cstdio>
const int N=1e7;
int a[N],s[N];
void S1(int n)
{
    for(int i=1; i<=n; i++)
        s[i]+=s[i-1];
}//一维

二维前缀和，可以理解的为在一个图形中i表示为行，j表示为列，用来计算一整个类图形的面积。计算前缀和也可以用递归s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];节省内存可以写作 s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];

alt

2.如图所示，如果要求x1y1到x2y2之间的那块面积，那么就要先用大的面积-蓝加黄-红加蓝+蓝；即s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1];

下面是模板：

#include <iostream>
#include<cstdio>
const int N=1e7;
using namespace std;
int a[100][100],s[100][100];
void S2(int m,int n)
{
    for(int i=1; i<=m; i++)
        for(int j=1; j<=n; j++)
            s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
}//二维
int m,n;
int main()
{
    scanf("%d %d",&m,&n);
    for(int i=1; i<=m; i++)
        for (int j=1; j<=n; j++)
            scanf("%d",&a[i][j]);
    S2(m,n);
    int x1,x2,y1,y2;//开始划定区间
    scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
    printf("%d\n",s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]);

    return 0;
}

zuo

差分：

差分可以看做是前缀和的逆运算。设b为a的差分。则a[i]=b[1]+b[2]+......b[i];差分的主要作用是在原数组同时+1只需要把差分的某一个+1然后a中的所有数字都会加1，把时间复杂度从o（n）变成o（1）。极大地缩减了计算时间。差分的计算同样可以通过递归算出。一种是b[n]=a[n]-a[n-1];另一种见母版。在进行差分计算，如果要在[l,r]中都加上c，则只用把b[l]+c,且把b[r+1]-c（用来抵消前面加c的效果，可以用下图表示）

alt

下面是模板：

#include <iostream>
#include<cstdio>
using namespace std;
const int N =1e7;
int n,m;
int a[N],b[N];
void insert1(int l,int r,int c)
{
    b[l]+=c;
    b[r+1]-=c;
}
int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1; i<=n; i++) scanf("%d",&a[i]);

    for(int i=1; i<=n; i++)insert1(i,i,a[i]); //算差分，会将b中先减去a[i-1]在加上a[i]

    while (m--)
    {
        int l,r,c;
        scanf("%d %d %d",&l,&r,&c);
        insert1(l,r,c);
    }
    for(int i=1; i<=n; i++) b[i]+=b[i-1];//求b的前缀和，即求改变后的a[i]
    for(int i=1; i<=n; i++) printf("%d",b[i]);
    return 0;
}

关于b[l]+c之后为什么后面加上c的问题？
因为在最后会重新算新的数组是通过加前一项得到的，所以在b[i]+c之后要将全部的东西加入到原来的数组中去，所以后面在不需要的地方需要-c。
二维差分和二维前缀和类似，计算时要划定区间进行计算，与前缀和不同的是，要用后面的图形。算差分的时候也有了调整，即b[i][j]=b[i-1][j]+b[i][j-1]-b[i-1][j-1]；

下面是模板：

#include <iostream>
#include<cstdio>
using namespace std;
const int N =1e7;
int x[100][100],y[100][100];
void insert2(int x1,int x2,int y1,int y2,int c)//二维
{
    y[x1][y1]+=c;
    y[x2+1][y1]-=c;
    y[x1][y2+1]-=c;
    y[x2+1][y2+1]+=c;
}

【算法】前缀和、差分

写在最前面：

记录：

前缀和：

差分：