背景

当你有一个数组，你要频繁地向里面的不同区间的数字进行加减的操作，
比如说{3，1，4，1，5，9}，你要向[0,2]减去二,
变成{1，-1，2，1，5，9}，然后向[1,3]加上2，
变成{1，1，4，3，5，9}，然后向[4,5]减去4
变成{1，1，4，3，1，4}，然后向[3,3]减去2……??????
当这种操作数量足够多，需要频繁的区间更新，如果我们使用简单的遍历，对这些数字进行加减，那速度会非常慢。

解决方案

使用一维差分

差分数组：

对于一个给定的原始数组 nums，我们构造一个相同长度的差分数组 diff，其中：
对要操作的区间开始的数字进行操作，对操作结束后的数字进行反向操作。
作为一个差分数组diff，记录区间更新，在全部操作结束后，我们只需要对原数组进行一次遍历，让diff的后一位,累加到原数组里面，那么在区间内所有的数都会受到diff影响，在区间后，由于diff的反向操作，会抵消掉区间更新。

例题

洛谷 P2367 语文成绩

题目背景

语文考试结束了，成绩还是一如既往地有问题。

题目描述

语文老师总是写错成绩，所以当她修改成绩的时候，总是累得不行。她总是要一遍遍地给某些同学增加分数，又要注意最低分是多少。你能帮帮她吗？

输入格式

第一行有两个整数 $n$，$p$，代表学生数与增加分数的次数。

第二行有 $n$ 个数，$a_1 \sim a_n$，代表各个学生的初始成绩。

接下来 $p$ 行，每行有三个数，$x$，$y$，$z$，代表给第 $x$ 个到第 $y$ 个学生每人增加 $z$ 分。

输出格式

输出仅一行，代表更改分数后，全班的最低分。

输入输出样例 #1

输入 #1

1
2
3
4
3 2
1 1 1
1 2 1
2 3 1

输出 #1

1
2

说明/提示

对于 $40%$ 的数据，有 $n \le 10^3$。

对于 $60%$ 的数据，有 $n \le 10^4$。

对于 $80%$ 的数据，有 $n \le 10^5$。

对于 $100%$ 的数据，有 $n \le 5\times 10^6$，$p \le n$，学生初始成绩 $ \le 100$，$z \le 100$。

我的答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<iostream>  
#include<algorithm>  
int main() {  
int n = 0, p = 0;  
std::cin >> n >> p;  
int arr[n];  
int diff[n+2];  
for (int i = 0;i < n;i++) {  
std::cin >> arr[i];  
}  
for(int i=0;i<n+2;i++){  
diff[i]=0;  
}  
for(int i =0;i<p;i++){  
int start=0;  
int end=0;  
int plus=0;  
std::cin>>start>>end>>plus;  
int left=start-1;  
int right=end;  
diff[left]+=plus;  
diff[right]-=plus;  
}  
// for (int i = 0;i < p;i++) {  
//     int start = 0, end = 0, plus = 0;  
//     std::cin >> start >> end >> plus;  
//     for (int j = start - 1;j < end;j+=2) {  
//         arr[j] += plus;  
//         arr[j+1]+=plus;  
//     }  
// }  
int sum=0;  
for(int i=0;i<n;i++){  
sum+=diff[i];  
arr[i]+=sum;  
}  
int min = arr[0];  
for (int i = 0;i < n;i++) {  
min = std::min(arr[i], min);  
}  
std::cout << min << std::endl;  
return 0;  
}

（PS：第一次写知识点总结和题解，感觉有点水，而且代码有屎，算了，自己看懂就行，嘻嘻）