差分思想与实际应用
欢迎来到萧云纹的编程随笔，本片我们将讨论差分思想。
差分思想
差分思想，一个用于优化频繁大区间修改的思想，具体如下：
设数组val、差分数组differ，val存放初始值，而differ[i]存储的就是val[i]和val[i - 1]的差，所以
①differ[i] = val[i] - val[i - 1]
（当i = 0时differ = 0）
根据①，很容易推出
②val[i] = differ[0] + differ[1] + ...... +differ[i];
推理过程：展开②等号右侧，即为
val[i] = 0 + val[1] - val[1] + val[2] - val[2] + val[3] + ...... + val[i - 1] - val[i - 1] + val[i]
= val[i]（抵消）
此时，如果我们想使得val数组的x~y全部加上k，因为val[x+1]~val[y]中每一位数和它前面的一个数的差不变，只有val[x],val[y+1]和其前面一位的差改变了，所以使val数组的x~y全部加上k这个操作和将differ[x]加上k，differ[y + 1]减去k这个效率更高的操作是等价的。
但是如果我们使用差分思想优化了区间的修改效率，使其变成了一个常数级的操作，但是对val[i]的访问因为需要使用到②式，使其效率变为了O(i)，这是差分思想的一个劣势。
不多说了，直接开码！
题目描述
输入一串数，允许对其进行两个操作：
操作①：输入x、y、k，给val[x]~val[y]间的每一个数字加上k
操作②：输入i，输出val[i]的值
输入输出格式
输入格式：
第一行输入两个数N、M，以空格隔开，分别代表val数组中数的个数，和总操作的个数。
第二行输入N个数，是val数组每一位的值，下标从1开始，以空格隔开。
下面从第3行到第m+三行，输入命令，命令的格式如下：
操作①：1 x y k。以空格隔开，给val[x]~val[y]间的每一个数字加上k
操作②：2 i。以空格隔开，输出val[i]的值
输出格式：
一共m行，即操作②的结果（操作①没有输出）
输入输出样例
输入样例#1：
5 5
1 5 4 2 3
1 2 4 2
2 3
1 1 5 -1
1 3 5 7
2 4
输出样例#1： 复制
6
10
题目解法：
C++代码，建议先自己思考/写代码再阅读以下部分。
操作①代码：
inline void Operator1(int *arrayPtr)
{
int l, r, v;
scanf("%d%d%d", &l, &r, &v);
arrayPtr[l] += v;
arrayPtr[r + 1] -= v;
}
操作②代码：
inline void Operator2(int *arrayPtr)
{
int index, temp = 0;
scanf("%d", &index);
for(int i = 0; i <= index; i++) {
temp += arrayPtr[i];
}
printf("\n%d\n", temp);
}
总体：
#include<bits/stdc++.h>
using namespace std;
inline void Operator1(int *arrayPtr)
{
int l, r, v;
scanf("%d%d%d", &l, &r, &v);
arrayPtr[l] += v;
arrayPtr[r + 1] -= v;
}
inline void Operator2(int *arrayPtr)
{
int index, temp = 0;
scanf("%d", &index);
for(int i = 0; i <= index; i++) {
temp += arrayPtr[i];
}
printf("\n%d\n", temp);
}
int main()
{
int n, m;
scanf("%d%d", &n, &m);
int val[n + 5], differ[n + 5];
differ[0] = 0;
val[0] = 0;
for(int i = 1; i <= n; i++) {
scanf("%d", &val[i]);
differ[i] = val[i] - val[i - 1];
}
int oper;
while(m--) {
scanf("%d", &oper);
if(oper == 1) {
Operator1(differ);
}
else {
Operator2(differ);
}
}
return 0;
}
这篇随笔到此结束，有什么问题欢迎私信我或者在评论区提出，我们下次再会。
