写在前面

对于前缀和的基本原理,基本上都可以用容斥原理推导而来,前缀和是一种重要的预处理,能大大降低时间复杂度

一维前缀和

例题:
给定$n$个整数,给定$q$个询问,每次询问一个$k$,请快速回答出$\sum\limits_{i=1}^ka_i$($n\leq10^{5}$)

初步分析

此题我们很快会想到一种思路-模拟,代码也很好写:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 +5;
int n,q,k,a[N];
int main()
{
scanf("%d %d",&n,&q);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
while(q--)
{
scanf("%d",&k);
int ans = 0;
for(int i=1;i<=k;i++)
{
ans += a[i];
}
printf("%d\n",ans);
}
return 0;
}

但是,经过我们分析,这种算法的时间复杂度为$O(n^{2})$,会TLE.

进一步分析

我们有没有什么办法来降低复杂度呢?
我们令$sum_{i}$表示前$i$个数的和,那么我们可以很容易得到递推式:
$$sum_{i}=sum_{i-1}+a_{i}$$
这样只需要一开始$O(n)$计算,$O(1)$查询即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 +5;
int n,q,k,a[N],sum[N];
int main()
{
scanf("%d %d",&n,&q);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
sum[i] = sum[i - 1] + a[i];
}
while(q--)
{
scanf("%d",&k);
printf("%d\n",sum[k]);
}
return 0;
}

例如:

样例输入
1
2
3
4
5
5 3
1 3 2 4 6
3
4
1
样例输出
1
2
3
6
10
1

二维前缀和

例题:
给出一个矩阵$a$,请快速回答出以$a_{1,1}$为左上角,$a_{i,j}$为右下角的矩阵内数字总和。

分析

第一眼可能是暴力,但有没有什么更快的办法呢?
同样,我们定义一个数组$sum$,$sum_{i}{j}$表示以$a_{1,1}$为左上角,$a_{i,j}$为右下角的矩阵内数字总和。
那么,我们可以通过容斥原理来理解,见下图:
容斥原理求二维前缀和
通过图片,我们就很容易得到递推式:$sum_{i,j}=sum_{i-1,j}+sum_{i,j-1}-sum_{i-1,j-1}+a_{i}$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 5;
int n,m,a[N][N],sum[N][N];
int main()
{
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
scanf("%d",&a[i][j]);
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] -sum[i - 1][j - 1] + a[i][j];
}
}
int i,j;
scanf("%d %d",&i,&j);
printf("%d",sum[i][j]);
return 0;
}

例如:

样例输入
1
2
3
4
5
3 3
1 4 2
5 2 7
8 2 1
2 3
样例输出
1
21

差分数组

定义

差分,是一种和前缀和相对的策略。————出自oiwiki

对于一个$a$数组,我们之前已经学习过前缀和$sum$,现在我们来讲一个另一个东东————差分
我们定义一个查分数组$b$,令$b_{i}=a_{i}-a_{i-1}$如:
例子
然后,经过我们的日思夜想,反复琢磨,废寝忘食的努力,我们发现一个结论:
差分数组的前缀和就等于原数组!
验证一下:

例子
1
2
b数组的前缀和:
1,2,4,7

再来证明一下:
设原数为:
$$a_{1},a_{2},a_{3}…a_{n}$$
则差分数组为:
$$a_{1},a_{2}-a_{1},a_{3}-a_{2}…a_{n}-a_{n-1}$$
求前缀和:
$$a_{1},a_{2},a_{3}…a_{n}$$
其实也很好推啦

例题

例题
1
2
3
4
5
6
有n个数。

m次操作,每一次操作,给定l,r,k.将l~r区间的所有数增加k;

最后有q个询问,给你 l,r ,每一次询问求出l~r的区间和。

一眼看过去,全是线段树,树状数组
但——今天讲的是差分。。。。。。
先给结论吧。
同样我们先定义一个差分数组$b$,则将$[l,r]$增加$k$只需要将$b_{l}+k$以及$b_{r+1}-k$
证明:
还是原来那个例子
例子
我们要给$[2,3]+5$,则改变后的差分数组即为$1,6,2,-2$
推导出原数组:$1,7,9,7$
不难看出,结论成立,所以说我们就可以$O(1)$查询了
代码就很好写了:

例题代码
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
#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 +5;
int n,m,l,r,k,q;
int a[N],bsum[N],b[N],sum[N];
int main()
{
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
b[i] = a[i] - a[i - 1];
}
while(m--)
{
scanf("%d %d %d",&l,&r,&k);
b[l] += k,b[r + 1] -= k;
}
for(int i=1;i<=n;i++)
{
bsum[i] = bsum[i - 1] + b[i];
sum[i] = sum[i - 1] + bsum[i];
}
scanf("%d",&q);
while(q--)
{
scanf("%d %d",&l,&r);
printf("%d\n",sum[r] - sum[l - 1]);
}
return 0;
}
样例输入
1
2
3
4
5
6
7
8
9
5 3
1 4 2 6 8
1 2 4
4 6 2
1 5 1
3
1 2
1 5
3 4
样例输出
1
2
3
15
38
12

应该没问题吧~~