基础算法前缀和与差分

前言

本次博客会介绍一维和二维的前缀和，以及一维二维差分的基本使用，尽量画图，多使用配合文字

使大家理解，希望有所帮助吧

一维前缀和

问题描述

这里有一个长度为n的数组，我们要算出【2,5】区间的元素和

暴力思路

要计算一个数组区间的和可以直接把它遍历一遍，其实相信大家肯定可以敲出这个简单的代码

我们这里简单的敲一敲

//这里可以改变数组的大小
#define N 10
int main()
{
	int arr[N] = { 1,2,3,4,5,6,7,8,9,10 };
	printf("请输入两个数表示区间");
	//表示两个区间
	int left;
	int right;
	long long sum = 0;
	scanf("%d %d",&left,&right);
	for (int i = left; i <= right; i++)
		sum+=arr[i];
	printf("%lld",sum);
	return 0;
}

这里的时间复杂就是0(n)

如果我们要计算m次区间和的话时间复杂度为o(n*m)

前缀和思路

我们可以直接用一个sum数组分别去记录它的前n项和

数组的下边代表项数

举个例子

有一个数组 1 2 3 4 5 6 7 8 9 10

那么它的sum数组为 1 3 6 10 15 21 28 36 45 55

每一个元素都是前n项和数组的下标+1代表几个元素的和

公式 sum[i]=sum[i-1]+arr[i];

这里是递推式，后一项由前一项得到，算了怕大家不懂

sum[0]=arr[0]

sum[1]=sum[0]+arr[1]

sum[2]=sum[1]+arr[2]

```````````

这下该懂了吧，我们可以通过sum数组来求区间和

看图

大家看到了，我们只要sum[right]-sum[left-1]就可以解决问题 o(1)

区间分析

大家看如果是[0,5]区间那么他就有可能会出现越界的情况呀

毕竟是sum[5]-sum[-1],那不就错了吗

所以我们的sum数组应该从1开始的我们默认让sum[0]=0

这样就不会出现区间问题，而此时区间代表的就不是数组下标而是第几个数到第几个数

看代码吧

int sum[11] = {0};
int main()
{
	int arr[10] = { 1,2,3,4,5,6,7,8,9,10 };
	int l, r;
	printf("请输入两个数,表示左右区间");
	scanf("%d %d", &l, &r);
	int size = sizeof(arr) / sizeof(arr[0]);
	//计算前缀和数组
	for (int i = 1; i <=size; i++)
	{
		sum[i] = sum[i - 1] + arr[i-1];
	}
	int result = sum[r] - sum[l - 1];
	printf("%d",result);
	return 0;
}

这样就可以降低时间复杂度了

一维差分

问题描述

有一个数组，我们要对 [left,right] 区间的元素进行加减操作操作m次

暴力思路

还是这样，我们还是遍历一遍区间，然后进行操作

其实暴力代码还是一样的，这里还是别懒了，再给大家操作一遍

//这里可以改变数组的大小
#define N 10
int main()
{
	int arr[N] = { 1,2,3,4,5,6,7,8,9,10 };
	printf("请输入两个数表示区间");
	//表示两个区间
	int left;
	int right;
	scanf("%d %d",&left,&right);
    printf("请输入操作数");
    int a;
    scanf("%d",&a);
	for (int i = left; i <= right; i++)
		arr[i]+=a;
	for(int i=0;i<N;i++)
        printf("%d",arr[i]);
	return 0;
}

差分思路

我们先算一遍差分数组

比如有一个数组arr[10]={1,2,3,4,5,6,7,8,9,10};

我们先算一个d[10]数组

d[0]=arr[0] d[1]=arr[1]-arr[0] d[2]=arr[2]-arr[1] d[3]=arr[3]-arr[2]

······d[9]=arr[9]-arr[8]

那么d[10]={1,1,1,1,1,1,1,1,1,1};

差分数组的性质

1 大家发现没，差分和前缀和是逆运算，也就是我们可以通过前缀和的公式计算差分数组得到原数组

2 差分数组的前面元素加上或减去一个数，在进行前缀和后会把所加的数的影响给到后面的元素

可以举例

比如一个差分数组

0 0 0 0 0 0 0 0 0 0

我们让第一个数加上一个1 变成

1 0 0 0 0 0 0 0 0 0

通过前缀和，所求的原数组为

1 1 1 1 1 1 1 1 1 1

这种影响会从前到后影响

对吧，那么如何解决问题呢，只要控制影响，利用差分数组的逆过来求前缀和数组

最后把结果加入到所求的数组中完成任务

那我们还是画个图，来理解

接下来看代码

//差分
//差分可以让某个区间全体加上或减去一个数
//除去差分数组可达到o(1)的时间复杂
int sub[20] = {0};
void fun(int left, int right, int num)
{
	sub[left] += num;
	sub[right+1]-=num;//只要数组的大小大于计算数组就不用担心越界问题
}
int main()
{
	int arr[10] = { 1,2,3,4,5,6,7,8,9,10 };
	int size = sizeof(arr) / sizeof(arr[0]);
	//差分其实是前缀的逆运算
	//也就是可以说差分后再前缀可以得到原来的数组
	//所以完全可以不用去算差分数组而是创建一个数组把它当成
	//差分数组，再求前缀和，把它与原来的数组相加可以得到结果
	fun(1, 2, 5);
	for (int i = 1; i < size; i++)
	{
		sub[i] += sub[i - 1];
	}
	for (int i = 0; i < size; i++)
		arr[i] += sub[i];
	for (int i = 0; i < size; i++)
		printf("%d ", arr[i]);
	return 0;
}