一、基本概念

现给一数组 A，则：

前缀和：新建一数组B，数组中每一项B[i]保存A中[0…i]的和；
后缀和：新建一数组B，数组中每一项B[i]保存A中[i…n-1]的和；
前缀积：新建一数组B，数组中每一项B[i]保存A中[0…i]的积；
后缀积：新建一数组B，数组中每一项B[i]保存A中[i…n-1]的积；

1、一维前缀和

对于一维数组，前缀和sum[i]表示的是所有a[1……i]的和。

void init()
{
	for(int i = 1; i <= n; i++) 
		sum[i] = sum[i-1] + a[i];
}

一般用来求区间和：

int get(int l, int r) 
{
    return sum[r] - sum[l-1];
}

2、二维前缀和

对于二维数组，前缀和sum[i][k]表示的是所有 a[ i’ ][ k’ ]（1< = i’<=i, i <= k’<=k) 的和。
数组的前缀与后缀及差分

int init() 
{
    for(int i = 1; i <= n; i++) 
    {
        for(int j = 1; j <= m; j++) 
        {
            sum[i][j] = sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1] + a[i][j];
        }
    }
}

求右下角红色区间和：
数组的前缀与后缀及差分

int get(int x1, int y1, int x2, int y2) 
{
    return sum[x2][y2] - sum[x2][y1 - 1] - sum[x1 - 1][y2] + sum[x1 - 1][y1 - 1];
}

二、前缀和、前缀积的应用（例子）：

1、题目1：

给定浮点数组a，求一数组b，b[i]=a[0]a[1]…*a[i-1]a[i+1]…*a[n-1]，不能使用除法，不允许新开数组。

思路：

先求“后缀积”：

for(int i=n-1;i>=0;i--) 
	b[i]=a[i]*((i==n-1)?1:b[i+1]);

再求“前缀积”：

for(int i=0,j=1;i<n;j*=a[i++]) 
	b[i]=j*((i==n-1)?1:b[i+1]);

2、题目2：

求数组中连续一段和，绝对值最小？

思路：

前缀和的性质：

a[i]+a[i+1]+…+a[j] = sum[j]-sum[i-1]

前缀和排序，取最小

3、题目3：

把一个数组从中间p位置分开，使得a[0]+…+a[p-1]与a[p]+a[p+1]+…+a[n-1]差值最小？

思路：

前缀和-（总和-前缀和）= 2*前缀和-总和，是该公式最小；
如果都是非负数，可以采取“两头扫”的方法，和较小的那边多加一个数；

三、差分

问题：给你一串长度为n的数列a1, a2, a3…an，要求对任意的 a[L]~a[R] 进行m次如下操作（每次二选一）：

操作一：将a[L]~a[R]内的元素都加上P

操作二：将a[L]~a[R]内的元素都减去P

求修改后的序列a，最后再给出一个询问求a[L]-a[R]内的元素之和？

【分析】
这里需要一个辅助数组b，b用来储存每一次的修改操作。
若选择对[L, R]区间进行加值操作，在b[L]处加一个p，在b[R+1]处就减去一个p。
若选择对[L, R]区间进行减值操作，在b[L]处减一个p，在b[R+1]处就加去一个p。

（1）最后求序列的每个位置变成了多少？只需要求一下b数组的前缀和，然后和原数组按位相加就好。
（2）最后再给出一个询问求a[L]-a[R]内的元素之和？求出修改后的序列a的前缀和，再求区间和就好。

接下来手动模拟验证一下：

下标			1	2	3	4	5	6	7
数组a初值	2   5   6   4   3   7   8
操作：
2—5区间加5   2   10  11  9   8   7   8
2—6区间加6   2   16  17  15  14  13  8
1—4区间加4   6   20  21  19  14  13  8

数组b初值    0    0   0   0   0   0   0
相同操作：
2—5区间加5   0    5   0   0   0  -5   0
2—6区间加6   0   11   0   0   0  -5   -6
1—4区间加4   4   11   0   0  -4  -5   -6

b的前缀和    4   15   15  15  11   6   0

可见，a的初值加上b的前缀和就是修改后a的值

原理明白后，代码如下：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+9;
int a[maxn],b[maxn];
int main()
{
	int i,j,k,n,m,p;
	cin>>n>>m;
	for(i=1;i<=n;i++)
	{
		cin>>a[i];	//给数组a赋值
	}
	for(i=1;i<=m;i++)
	{
		int L,R,t;
		cin>>t>>L>>R>>p;
		if(t==1)	//选择操作一
		{
			b[L]+=p;b[R+1]-=p; //仔细想想为什么b[R+1]要减去p 
		}
		else	//选择操作二
		{
			b[L]-=p;b[R+1]+=p;
		}
	}
	int add=0;
	for(i=1;i<=n;i++)	//直接求第二问
	{
		add+=b[i];
		a[i]+=a[i-1]+add;
	}
	int x,y;
	cin>>x>>y;
	cout<<a[y]-a[x-1]<<endl;
}

在操作1时b[R+1]要减去p，是因为操作1只需对[L,R]区间里的数加p，[R+1, n]这个区间里的数没必要加p，所以需要减掉p。

1、一维差分

我们对 [L, R] 区间进行加num操作，在b[L]处加上num，在b[R+1]处减去num

void init(int l,int r,int num) //数组b保存修改操作
{
    b[l] += num, b[r + 1] -= num;
}

int get() //求得数组b的前缀和
{
    for(int i = 1; i <= n; i++) {
        sum[i] = sum[i-1] + b[i];
    }
}

2、二维差分

二维差分与一维差分类似，需要注意怎么保存修改操作

void init(int x1, int y1, int x2, int y2, int num) //数组sum保存修改的操作
{
    sum[x1][y1] += num;
    sum[x1][y2 + 1] -= num;
    sum[x2 + 1][y1] -= num;
    sum[x2 + 1][y2 + 1] += num;
}

void get() 	//求得数组sum的前缀和，此时的sum就是前缀和
{
    for(int i = 1; i <= n; i++) 
    {
        for(int j = 1; j <= n; j++) 
        {
            sum[i][j] += sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1];
        }
    }
}

3、树上差分

（1）点差分

对 u 到 v 的路径上的点 +num
用来求 - 已知路径求树上所有节点被路径覆盖次数

int init(int u, int v, int num) {
    dis[u] += num;
    dis[v] += num;
    dis[lca(u,v)] -= num;
    dis[f[lca(u,v)]] -= num;
}

（2）边差分

对 u 到 v 的路径上的边 +num
用来求 - 已知路径求被所有路径覆盖的边
dis[i] 表示以i节点为儿子的边

int init(int u, int v, int num) {
    dis[u] += num;
    dis[v] += num;
    dis[lca(u,v)] -= 2 *num;
}

最后dfs遍历一遍

void dfs(int x) {
    for(int i = head[u]; i; i = e[i].next) {
        int v = e[i].v;
        if(v != f[x][0]) {    //f[x][0] 为倍增数组 
            dfs(v);
            dis[x] += dis[v];
        }
    }
}

数组的前缀与后缀及差分