当前位置：首页 > article >正文

【算法】差分思想：强大的算法技巧

article 2024/9/24 8:33:22

📢博客主页：https://blog.csdn.net/2301_779549673
📢欢迎点赞 👍 收藏 ⭐留言 📝 如有错误敬请指正！
📢本文由 JohnKi 原创，首发于 CSDN🙉
📢未来很长，值得我们全力奔赴更美好的生活✨

在这里插入图片描述

文章目录

📢前言
🏳️‍🌈一、差分思想概述
🏳️‍🌈二、差分思想的优缺点
🏳️‍🌈例题题解
👥总结

📢前言

大家可以先看一下题目
在这里插入图片描述

在这里插入图片描述
由于随着订单数量的增加，每天可用教室的数量一定单调下降。
因此我们可以二分出最后一天没出现负值的订单编号。

剩下的问题是如何快速求出经过若干订单后，每天所剩的教室数量。
每个订单的操作是 [Li,Ri]全部减去 di

因此我们可以用差分来加速处理过程。

🏳️‍🌈一、差分思想概述

在 C++ 中，差分思想主要涉及差分数组和原数组的关系。差分数组也是一个数组，定义为 $d [i] = a rr [i] - a rr [i - 1] (i! = 0)$ ，且 $d [i] = 0$ ，其中 arr[] 即为原数组。例如，有原数组 :9 3 5 2 7，对应的差分数组 :9 -6 2 -3 5。可以看出，差分数组的第一个值等于原数组第一个值，而其他位置的值等于原数组对应位置的值减去前一个位置的值。

差分数组的精髓在于可以通过其前缀和得到原数组。假设差分数组为 b ，原数组为 a ，那么 $a [i] = b [i] + a [i - 1]$ 比如，若 i=1 ，那 a[1] = b[0] + b[1] ；
若 i=2 ，那 a[2] = b[0] + b[1] +b[2]；

通过这种关系，可以利用差分数组在 O(1) 的时间复杂度内将区间内的元素都加上某个数。例如输入一个长度为 n 的整数序列，有频繁区间修改操作时，如让第 1 个数到第 1000 万个数每个数都加上 1，如果采用暴力方法遍历区间，时间复杂度是 O(n) ，效率非常低。

而使用差分数组，只需要对差分数组中的两个位置进行修改即可实现区间修改，大大降低了时间复杂度O(1)。比如，在区间 [l,r] 上所有的数值都加上常数 c ，只需要将 b[l] = b[l] + c ，然后在 b[r+1] = b[r+1] - c ，这样就把一连串的循环遍历修改转变为了对两个位置数字的修改，效率大大提升。

🏳️‍🌈二、差分思想的优缺点

差分思想在多个方面展现出显著的优势。

首先，在简化运算方面，差分数组能够将对区间元素的复杂操作转化为对差分数组中特定位置的简单修改。例如，当需要给一个区间 [l,r] 上的数组加一个常数 c 时，传统方法需要依次遍历区间内的每个元素进行加法操作，时间复杂度为 O(n) 。而利用差分数组，只需对差分数组中的两个位置进行修改，即 b[l] = b[l] + c 和 b[r+1] = b[r+1] - c ，时间复杂度降低至 O(1) 。这种简洁高效的操作方式在处理大规模数据和频繁的区间修改操作时优势尤为明显。

其次，在提高效率方面，对于包含大量区间修改操作的场景，C++ 差分思想能够极大地提高程序的执行效率。以处理长度为 n=100000 的整数序列为例，假设有 m=1000 个操作，每个操作都是对一个区间进行修改。如果使用传统方法，每次操作都需要遍历区间内的元素，总的时间复杂度将高达 O(m * n) 。而采用差分数组，每次操作只需要对两个位置进行修改，总的时间复杂度降低为 O(m + n) 。通过对比可以看出，差分数组在处理大量区间修改操作时效率提升巨大。

然而，差分思想也并非完美无缺。

虽然使用差分思想优化了区间的修改效率，使其变成了一个常数级的操作，但对原数组的访问效率却受到了一定的影响。因为对原数组中某个元素的访问需要通过差分数组的前缀和来计算，时间复杂度变为了 O(i) 。例如，当需要获取原数组中第 i 个元素的值时，需要计算差分数组中前 i 项的和，这在一定程度上增加了访问原数组的时间成本。

综上所述，C++ 差分思想在简化运算和提高效率方面具有明显优势，但在访问原数组时也存在一定的局限性。在实际应用中，需要根据具体情况权衡利弊，选择合适的方法来处理数据。

🏳️‍🌈例题题解

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<iostream>
#include<cstring>

using namespace std;

typedef long long LL;
const int N = 1000001;

int n, m;
int r[N];
int d[N], s[N], t[N];
LL e[N];

bool check(int mid)
{
	memset(e, 0, sizeof(e));

	for (int i = 1; i <= mid; i++)
	{
		e[s[i]] += d[i];
		e[t[i] + 1] -= d[i];
	}
	for (int i = 1; i <= n; i++)
	{
		e[i] += e[i - 1];
		if (e[i] > r[i])
			return false;
	}
	return true;
}

int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &r[i]);
	}
	for (int i = 1; i <= m; i++)
	{
		scanf("%d%d%d", &d[i], &s[i], &t[i]);
	}
	int L = 0, R = m;
	while (L < R)
	{
		int mid = L + (R - L + 1) / 2;
		if (check(mid))
			L = mid;
		else
			R = mid -1;
	}
	if (R == m)
		printf("%d", 0);
	else
		printf("%d\n%d", -1, R + 1);
}