原文来自我的博客:www.dorkyfox.com,转载引用请注明!!!
差分是前缀和的逆运算。如果将前缀和看作数列an的前n项和Sn,那么差分就是通过Sn求an。
原数组: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
思路:
::: 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(n2)
对于需要多次加常数的,可以像上面代码这样处理。
:::
差分函数 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