差分

差分算法

1、介绍
一般地，差分主要用于让一个序列某一特定范围内的所有值都加上或减去一个常数。

所以差分往往应用于线性的场合，即一维数组的环境，但是除此之外，差分还可以应用于二维数组，但是相比较一维数组，应用的较少。

2、定义
差分可以简单的看成序列中每个元素与其前一个元素的差。

3、差分与前缀和

const int N = 100010;
int n; //n数组长度
//定义两个一维整形数组 a为原数组，b为差分数组
int a[N],b[N];  

//根据定义可知
b[i] = a[i] - a[i-1];
//稍微具体
b[1] = a[1];
b[2] = a[2] - a[1];
b[3] = a[3] - a[2];
...
b[i] = a[i] - a[i-1];

//转化一下，求数组b的前缀和,根据上面公式可得
 b[1]+b[2]+b[3]+...+b[i]
= a[1]+(a[2]-a[1])+(a[3]-a[2])+...+(a[i]-a[i-1])
= a[i]

//由此可知，原序列为差分序列的前缀和序列
a[i] = b[1]+b[2]+b[3]+...+b[i];

• 一般地，我们认为原序列就是差分序列的前缀和，所以把差分看做前缀和的逆运算

二、一维差分
1、定义
一维差分是指给定一个长度为n的序列a，要求支持操作pro(l,r,c)表示对a[l]~a[r]区间上的每一个值都加上或减去常数c，并求修改后的序列a。

2、作用
让一个序列中某个区间内的所有值均加上或减去一个常数。

可以将对a数组任意区间的同一操作优化到O(1)。

//区间[l,r]中的所有值都加上常数c
b[l] += c;
b[r+1] -= c;
 

//想象下：
因为：b[l]=a[l]-a[l-1];，而前面的b[1]_{b[l-1]都没有发生变化，所以$a[l-1]=b[1]+…+b[l-1]$不变，所以只可能是a[l]加了c。若要使a[l]}a[r]区间都加上c，则：

b[l+1]=a[l+1]-a[l]

......

b[r]=a[r]-a[r-1]

这中间所有的b中元素统统不变（被减数和减数同时加了c）

而

b[r+1]=a[r+1]-a[r]

因为要使得a[r]+c，而a[r+1]不变，则有b[r+1]-=c

最后对b数组求前缀和，所以以上程序可以实现在a[l]~a[r]里面同时加上c

for(int i = 1; i <= n; i++)
{
    b[i] += b[i-1];
    printf("%d ",b[i]);
}

例题：

语文成绩

题目背景

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

题目描述

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

输入格式

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

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

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

输出格式

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

样例 #1

样例输入 #1

3 2
1 1 1
1 2 1
2 3 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。