原文来自我的博客：www.dorkyfox.com，转载引用请注明！！！

差分是前缀和的逆运算。如果将前缀和看作数列a_n的前n项和S_n，那么差分就是通过S_n求a_n。

原数组：a[1]、a[2]、a[3]、a[4]、a[5]

差分数组：a[1]、a[2]-a[1]、a[3]-a[2]、a[4]-a[3]、a[5]-a[4]

一维差分

应用：快速地对数组中某一部分连续的元素加上一个常数。

示例：

给数组 a a a 中的第 l 个元素到第 r 个元素_{（包括l和r）}中的每一个元素都加 k

思路：

1. 首先对原数组 a a a 求差分数组 b b b
2. b [ l ] b[l] b[l] 加 k k k ， b [ r + 1 ] b[r+1] b[r+1] 减 k k k
3. 最后对数组 b b b 求前缀和即可

::: details 具体题目

洛谷-P2367 语文成绩

#include<iostream>
#include<numeric>
#include<algorithm>
using namespace std;
int n, p, x, y, z, a[6000000];
int main()
{
	cin >> n >> p;
	for (int i = 1; i <= n; i++)cin >> a[i];
	adjacent_difference(a + 1, a + n + 1, a + 1);//差分函数
	while (p--)
	{
		cin >> x >> y >> z;
		a[x] += z; a[y+1] -= z;
	}
	partial_sum(a + 1, a + n + 1, a + 1);//前缀和函数
	cout << *min_element(a + 1, a + n + 1);//数组最小值函数
	return 0;
}

注意：

不要把 差分函数 和 前缀和函数 放在循环中，会大大增大时间复杂度 O(n)→O(n²)

对于需要多次加常数的，可以像上面代码这样处理。

:::

C++算法库

差分函数 std::adjacent_difference，定义在头文件 <numeric> 中。

adjacent_difference(first, last, d_first );

参数：

first, last	要求和的元素范围
d_first	目标范围起始；可以等于 first

计算 [first, last) 范围中每对相邻元素的第二个和第一个的差，并写入它们到始于 d_first 的范围。

示例：

#include<iostream>
#include<numeric>
using namespace std;
int main()
{
	int a[5] = { 1,2,3,4,5 };
	adjacent_difference(a, a + 5, a);
	for (int i = 0; i < 5; i++)cout << a[i] << ' ';
	return 0;
}

控制台返回：

1 1 1 1 1