前缀和与差分

Created2021-01-25Updated2021-02-03

前缀和与差分

前缀和

一、什么是前缀和？

  1. 一维前缀和：

有一个一维数组a和该数组的一维前缀和数组 s ，则 a和 s满足以下关系：
s[1]=a[1]，s[2]=a[1]+a[2]，s[n]=a[1]+a[2]+…+a[n];

  1. 二维前缀和：

二维数组的右下角单元格，存的是以它为右下角，以(1,1)为左上角的矩形区域的所有单元格的和。

二、前缀和的应用

前缀和是一种预处理方式，用于降低查询时的时间复杂度，可以很快的查询出子序列的和，子矩阵的和,常常与差分联系在一起。

三、如何得到前缀和？

一维前缀和：

很容易就可以发现：s[i]=s[i-1]+a[i];

代码实现如下：

预处理：

1
2
3
4
for(int i=1;i<=n;i++)
{
    s[i]=s[i-1]+a[i];
}

查询：

1
2
//[l,r]
sum = s[r]-s[l-1];

二维前缀和：

二维前缀和实际上就是一个矩阵内值的和，而矩阵又可以由两个行数或列数少一的子矩阵组合后，删去重合部分再加上右下角的值来构成（原理可画图推出，此处略）：

代码实现如下：

预处理：

1
2
3
4
5
for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++)
    {
		s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
    }

查询：

1
2
//左上角 x1,y1  右下角 x2,y2;
sum = s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1];

差分

一、差分的定义

定义 b[i]=a[i]-a[i-1]，那么b是a的差分数组，此时对b求前缀和可得到原数组a，由此可知差分和前缀和互为逆运算。（类比积分和微分）

二、差分的应用

前缀和数组能够将对原数组a的任意区间的区间和查询优化到O(1)，差分数组类似的可以将a数组的任意区间的同一种修改操作优化到O(1)。

三、差分的实现

差分数组的构造

原理：详见修改操作原理，构造实际上是在[1,1], [2,2] , … 区间内加上c=a[i]这个数。

1
2
3
4
for(int i=1;i<=n;i++)
{
	b[i]=a[i]-a[i-1];
}

对a数组的区间[l,r]同时加上c的操作：

原理：我们已经知道不修改的情况下对b数组求前缀和就可以得到原数组a的值了，那么+c修改后，在求l之后的前缀和时，b[l]会对它后面的 a[l], a[l+1], a[l+2],… 这些”前缀和“都造成+c的影响，因此为了消除r之后的这些影响，到 r+1 这里要减去c来抵消这种影响。

代码如下：

1
2
b[l]+=c;
b[r+1]-=c;

对b数组求前缀和即可得到原数组a （ 时间复杂度O(N) ）

1
2
3
4
for(int i=1;i<=n;i++)
{
	s[i]=s[i-1]+b[i];
}

差分完整模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<iostream>
#include<cstdio>
using namespace std;
int a[100050],b[100050];
int n,m;
void ins(int l,int r,int c)
{
    b[l]+=c;
    b[r+1]-=c;
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        ins(i,i,a[i]);
    }
    while(m--)
    {
        int l,r,c;
        cin>>l>>r>>c;
        ins(l,r,c);
    }
    for(int i=1;i<=n;i++)
    {
        b[i]+=b[i-1];
        cout<<b[i]<<" ";
    }
    return 0;
}

四、例题

acwing 798 差分矩阵 (二维 前缀和+差分)

输入一个n行m列的整数矩阵，再输入q个操作，每个操作包含五个整数x1, y1, x2, y2, c，其中(x1, y1)和(x2, y2)表示一个子矩阵的左上角坐标和右下角坐标。

每个操作都要将选中的子矩阵中的每个元素的值加上c。

请你将进行完所有操作后的矩阵输出。

输入格式

第一行包含整数n,m,q。

接下来n行，每行包含m个整数，表示整数矩阵。

接下来q行，每行包含5个整数x1, y1, x2, y2, c，表示一个操作。

输出格式

共 n 行，每行 m 个整数，表示所有操作进行完毕后的最终矩阵。

数据范围

1≤n,m≤1000,
1≤q≤100000,
1≤x1≤x2≤n,
1≤y1≤y2≤m,
−1000≤c≤1000,
−1000≤矩阵内元素的值 ≤1000

输入样例：

1
2
3
4
5
6
7
3 4 3
1 2 2 1
3 2 2 1
1 1 1 1
1 1 2 2 1
1 3 2 3 2
3 1 3 4 1

输出样例：

1
2
3
2 3 4 1
4 3 4 1
2 2 2 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int a[1050][1050],b[1050][1050];
int n,m,q;
void ins(int x1,int y1,int x2,int y2,int c)
{
    b[x1][y1]+=c;
    b[x2+1][y1]-=c;
    b[x1][y2+1]-=c;
    b[x2+1][y2+1]+=c;
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>a[i][j];
            ins(i,j,i,j,a[i][j]);
        }
    }
    while(q--)
    {
        int x1,y1,x2,y2,c;
        cin>>x1>>y1>>x2>>y2>>c;
        ins(x1,y1,x2,y2,c);
    }
    memset(a,0,sizeof(a));
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+b[i][j];
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cout<<a[i][j]<<" ";
        }
        cout<<endl;
    }
    return 0;
}

luogu P3368 树状数组2