信奥赛_NOIP/CSP——差分算法
前言：
在学习的过程中，对于一些有意思的算法的还是需要留意一下，这些算法有助于我们对解决现实问题有很大帮助，当然更有助于我们在参加一些比赛的时候思路开阔！！！
接下来我们来一起探究一下差分算法！并且对其性质的一些应用。
差分算法：
一维差分算法：
什么是差分？？
如果有一组数，或者称为一组数列。
a0 , a1 , a2 , a3 , a4 , a5 , a6 ,......, an （此时假设a0等于0，从a1开始放入需要的值）
从0下标一直到n下标，一共有n+1个数
此时有以下几组表达式，就是相邻两个数之间作差！
fin(1) = a1 - a0;
fin(2) = a2 - a1;
fin(3) = a3 - a2;
fin(4) = a4 - a3;
......
此时我如果想要求a1，a2 , a3 ，... , an 。
可以这样求：
a1 = fin(1)。
a2 = fin(2) + fin(1) = a1+fin(2)
a3 = fin(3)+fin(2)+fin(1) = a2+fin(3)
......
那么这样做有什么用呢？
此时就有如下的一个场景：
如果此时有n组数据(n>=1,n<=10^10),想要给这n组数据中的任意k组上面加上或者减上一个数(假设是m)，得到一个新的n个数的数组，那么此时应该怎么做？？
可能对于大多数人来说咋们直接对这一组(假设每组为n个数字)的每一个数进行遍历，每次加或者减m。
如图：
那么此时直接遍历之后每一个数+m即可,此时时间复杂度为O(n)。
但是此时难度升一级：
此时给多组(假设是n组，每组为3个数据)连续的数据进行+-m的操作。（此时每组没有重叠的部分！）
那么此时也可以利用上述的思路可以遍历每一组，之后给每一组+-m即可，此时时间复杂度为O(n)。
此时难度再次升级：
此时还是给多组(假设是n组，每组p个数据)数据进行+-m的操作。（此时每组中有重叠的部分！）
此时如果还是采用上述的思路，进行遍历逐一进行+-m，那么时间复杂度为O(n*p)!
那么此时n和p都非常大时，此时耗费的时间太长了！！
那么有没有办法将时间复杂度降为同样的O(n)呢？？
此时差分算法可以起到一定的作用！
此时可以创建一个差分数组，专门存放差分过后的值！(将需要进行+-m的部分，进行差分放在数组中！)
首先举个例子：
假设一个数列中存放的是0，1，2，3，4，5，6如果此时想要将2~5同时加1，此时就变
了0，1，3，4，5，6，6 。
那么此时原数列中2~5的差分过后为，0，1，1，1，1，1，6。
需要用到公式：
fin(1) = a1 - a0;
fin(2) = a2 - a1;
fin(3) = a3 - a2;
fin(4) = a4 - a3;
......
此时如果想要2~5同时+1，可以在最开始2对应的差分后的数字基础上+1即可
加之后变为：0，1，2，1，1，1，6.
最后需要还原为原数列：
就需要用到公式：
a1 = fin(1)。
a2 = fin(2) + fin(1) = a1+fin(2)
a3 = fin(3)+fin(2)+fin(1) = a2+fin(3)
......
还原之后为：
0，1，3，4，5，6，6
综上这个例子，可以推出差分的相关加减法的性质：
a0 , a1 , a2 , a3 , a4 , a5 , a6 ,......, an （此时假设a0等于0，从a1开始放入需要的值）
此时可以利用上述的性质可以对需要加减的部分
先进行差分
再进行加减
最后进行还原
此时上图的a1到a7需要进行加减，可以先进行差分：
之后对fin(1)和fin(4)进行+m和-m
最后对其进行还原
这个过程时间复杂度就可以降至O(n),非常方便！！
二维差分算法：
刚刚探究过以为差分的步骤和差分的加减法的性质！
此时如果该数组变为2维数组，该怎么处理？？
例如：
有以下场景：
有几块矩形，每块矩形的顶点都在每个放个的定点上，如果此时求这些矩形的面积之和应该怎么做？
此时应该怎么求这两个矩形的面积之和？？
可以想到有一种方法：
就是遍历两个矩形的每个方格，如果遍历到了就将其置为1，
最后遍历这个二维数组即可，用计数器最后返回其遍历为1的值，
题目如下：
代码如下：
#include<iostream>
using namespace std;
const int MAXN(1e4);
//保险期间，多创建一行一列
int a[MAXN + 1][MAXN + 1];
int main()
{
int n;
//输入n
cin >> n;
while (n--)
{
int x1, y1, x2, y2;
//输入x1,y1,x2,y2
cin >> x1 >> y1 >> x2 >> y2;
for (int i = x1+1; i <= x2; i++)
{
for (int j = y1+1; j <= y2; j++)
{
a[i][j] = 1;
}
}
}
int count(0);
//遍历
for (int i = 1; i <= MAXN; i++)
{
for (int j = 1; j <= MAXN; j++)
{
还原差分方程
//b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];
if (a[i][j] != 0)
{
count++;
}
}
}
cout<<count;
return count;
} 但是此时有一个缺点，还是如果几个重叠的部分，例如：
此时还是和一维差分有相同的问题，就是此时的时间复杂度又变为了O(p*n^2),
那么有没有什么方法降低时间复杂度？
尽量让其降低为O(n^2).
此时还是可以用到差分的思想：
此时还是一样的，如果存在一块矩形，那么这块矩形的中的每一格都应该是1。
以一小块举例：
此时，这一块矩形的每一格都是1，那么如何找到这四块的差分后的值？
公式为：
本身 + 对角格的值 - 左边格的值 - 上边格的值
此时可以推导一下这个格中的差分后的值与它相邻格差分后的值：
此时如果将其还原就会变成如下的形式：
还原公式：
本身 - 对角格的值 + 左边格的值 + 上边格的值
当然该算法需要注意的就是，所有的点都应该满足x >= 1,y >= 1，原因在于最左边一列与最上边一行需要一直保持为零为计算第一个位置的值做准备：
所以这道题可以进行简单的差分优化：
题目给出两组个对角的下标，假设就是左下标和右上标！
此时需要注意的就是，这个差分过后的位置应该找？
所以综上：
最后还需要还原，最后代码如下：
#include<iostream>
using namespace std;
const int MAXN(1e4);
//保险期间，多创建一行一列
int a[MAXN + 1][MAXN + 1];
//设计差分数组
int b[MAXN + 1][MAXN + 1];
int main()
{
int n;
//输入n
cin >> n;
while (n--)
{
int x1, y1, x2, y2;
//输入x1,y1,x2,y2
cin >> x1 >> y1 >> x2 >> y2;
//构建每一个图形的差分数组
b[x1 + 1][y1 + 1]--;
b[x2 + 1][y2 + 1]--;
b[x1 + 1][y2 + 1]++;
b[x2 + 1][y1 + 1]++;
}
int count(0);
//遍历
for (int i = 1; i <= MAXN; i++)
{
for (int j = 1; j <= MAXN; j++)
{
//还原差分方程还原
b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];
if (b[i][j] != 0)
{
count++;
}
}
}
cout << count;
return count;
}