基础算法———前缀和与差分

  • Post author:
  • Post category:其他



  1. 前缀和与差分的定义与联系


    设有数组{a

    n

    } = a

    1

    , a

    2

    , a

    3

    , ……,a

    n

    ; {b

    n

    } = b

    1

    , b

    2

    , b

    3

    , ……, b

    n


    且有a

    i

    = b

    1

    +b

    2

    +b

    3

    +……+b

    i


    则称a

    n

    为b

    n

    的前缀和,b

    n

    为a

    n

    的差分,且b

    n

    = a

    n

    – a

    n-1


  2. 用途


    前缀和的作用:已知某个数组的前缀和数组,可以快速求得该数组的某个区间片段和

    差分的作用:利用原数组的差分数组,快速使原数组某个区间片段的元素加上同一个数


  3. 在矩阵上的推广


    前缀和与差分可以从一位数组推广到二维数组(矩阵),快速求得子矩阵的和以及快速对子矩阵的元素同时加一个数


  4. 一维前缀和模板

s[i] = a[1] + a[2] + a[3] + …+a[i]

a[l] + … + a[r] = s[r] – s[l-1]


应用例题:前缀和


输入一个长度为n的整数序列。

接下来再输入m个询问,每个询问输入一对l, r。

对于每个询问,输出原序列中从第l个数到第r个数的和。


输入格式


第一行包含两个整数n和m。

第二行包含n个整数,表示整数数列。

接下来m行,每行包含两个整数l和r,表示一个询问的区间范围。


输出格式


共m行,每行输出一个询问的结果。


数据范围


1≤l≤r≤n,1≤n,m≤100000

−1000≤数列中元素的值≤1000


输入样例:


5 3

2 1 3 6 4

1 2

1 3

2 4


输出样例:


3

6

10

#include<iostream>

using namespace std;

const int N = 100010;

int n, m;
int a[N], s[N];		//此处a[0], s[0]被初始化为0

int main()
{
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i++) scanf("%d", &a[i]);	//数组从下标1开始存放,使s[n]也可以用s[i-1] + a[i]表示

	for(int i = 1; i <=n ; i++) s[i] = s[i-1] + a[i];	//初始化s[N]

	while(m--)
	{
		int l, r;
		scanf("%d%d", &l, &r);
		printf("%d\n", s[r] - s[l-1]);		//计算片段和并输出
	}

	return 0;
}		

  1. 二维前缀和模板

s[i][j] 是二维数组第i行第j列元素左上角所有元素的和

以(x

1

, y

1

)为左上角,(x

2

, y

2

)为右下角的子矩阵所有元素和为:

s[x2][y2] – s[x1 – 1][y2] – s[x2][y1 – 1] + s[x1 – 1][y1- 1];


应用例题:子矩阵的和


输入一个n行m列的整数矩阵,再输入q个询问,每个询问包含四个整数x1, y1, x2, y2,表示一个子矩阵的左上角坐标和右下角坐标。

对于每个询问输出子矩阵中所有数的和。


输入格式


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

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

接下来q行,每行包含四个整数x1, y1, x2, y2,表示一组询问。


输出格式


共q行,每行输出一个询问的结果。


数据范围


1≤n,m≤1000,1≤q≤200000,1≤x1≤x2≤n,1≤y1≤y2≤m

−1000≤矩阵内元素的值≤1000


输入样例:


3 4 3

1 7 2 4

3 6 2 8

2 1 2 3

1 1 2 2

2 1 3 4

1 3 3 4


输出样例:


17

27

21

#include<iostream>

using namespace std;

const int N = 1010;

int n, m, q;
int a[N][N], s[N][N];

int main()
{
	scanf("%d%d%d", &n, &m, &q);
	for(int i = 1; i <= n; i++)
		for(int j = 1; j<=m; j++)
			scanf("%d", &a[i][j]);

	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];	//初始化s[N][N]
	
	while(q--)
	{
		int x1, y1, x2, 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;	


		

  1. 差分模板

给区间[l, r]中的每个数都加上c:b[l] += c, b[r+1] -= c;


应用例题:差分


输入一个长度为n的整数序列。

接下来输入m个操作,每个操作包含三个整数l, r, c,表示将序列中[l, r]之间的每个数加上c。

请你输出进行完所有操作后的序列。


输入格式


第一行包含两个整数n和m。

第二行包含n个整数,表示整数序列。

接下来m行,每行包含三个整数l,r,c,表示一个操作。


输出格式


共一行,包含n个整数,表示最终序列。


数据范围


1≤n,m≤100000,1≤l≤r≤n,−1000≤c≤1000

−1000≤整数序列中元素的值≤1000


输入样例:


6 3

1 2 2 1 2 1

1 3 1

3 5 1

1 6 1


输出样例:


3 4 5 3 4 2

#include<iostream>

using namespace std;

const int N = 100010;

int n, m; 
int a[N], b[N];

//函数功能:使数组[l, r]区间每个数都加c
void insert(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++) insert(i, i, a[i]);		//初始化差分数组

	while(m--)
	{
		int l, r, c;
		scanf("%d%d%d", &l, &r, &c);
		insert(l, r, c);
	}

	for(int i = 1; i<=n; i++) b[i] += b[i-1];	//计算经过m次操作后的数组,存储在b[N]中。
	for(int i = 1; i<=n; i++) printf("%d ", b[i]);
	
	return 0;
}	

  1. 二维差分模板

给以(x1, y1)为左上角,(x2, y2)为右下角的子矩阵中的所有元素加上c:

S[x1, y1] += c, S[x2 + 1, y1] -= c, S[x1, y2 + 1] -= c, S[x2 + 1, y2 + 1] += c


应用例题:差分矩阵


输入一个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


输入样例:


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


输出样例:


2 3 4 1

4 3 4 1

2 2 2 2

#include<iostream>

using namespace std;

const int N = 1010;

int n, m, q;
int a[N][N], b[N][N];

void insert(int x1, int y1, int x2, int y2, int c)
{
	b[x1][y1] += c;
	b[x1][y2 + 1] -= c;
	b[x2 + 1][y1] -= c;
	b[x2 + 1][y2 + 1] += c;
}

int main()
{
	scanf("%d%d%d", &n, &m, &q);
	for(int i = 1; i<=n; i++)
		for(int j = 1; j<=m; j++)
			scanf("%d", &a[i][j]);
	 
	 for(int i = 1; i<=n; i++)
	 	for(int j = 1; j <= m; j++)
	 		insert(i, j, i, j, a[i][j]);	//初始化差分矩阵

	while(q--)
	{
		int x1, y1, x2, y2, c;
		scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &c);
		insert(x1, y1, x2, y2, c); //对以(x1, y1)为左上角,(x2, y2)为右下角的子矩阵中的所有元素加上c
	}

	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
			b[i][j] += b[i-1][j] + b[i][j-1] - b[i-1][j-1];	//计算b[N][N]的子矩阵和,即a[i][j],并储存在b[i][j]中

	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= m; j++) printf("%d ", b[i][j]); //输出计算经过m次操作后的矩阵
		puts(" "); //输出换行符
	}
	return 0;
}		
				

[^1]

注:为了方便计算,计算前缀和与差分时,一维数组与二维数组下标为零的元素全部初始化为0,使a[l] + … +a[r] = s[r] – s[l-1]恒成立


[^2]注:此文章所有代码均来自www.acwing.com



版权声明:本文为CSDN729180099原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。