差分操作正确性证明
本文是作者因题目写差分写挂了后随手总结的。
定义
对于一个长度为 \(n\) 的数组 \(a\)，定义其差分数组为 \(p\)，且 \(\forall 1\le i\le n,p_i=a_i-a_{i-1}(a_0=0)\)。
转化回原数列
给些式子就懂了。
根据定义：
\[p_1+p_2+p_3+\cdots +p_k\\
=a_1+(a_2-a_1)+(a_3-a_2)+\cdots +(a_k-a_{k-1})\\
=a_k
\]
所以，\(a_k=\sum_{i=1}^k p_i\)。
\[a_k=\sum_{i=1}^k p_i\\
a_k=\sum_{i=1}^{k-1}p_i+p_k\\
a_k=a_{k-1}+p_k
\]
另一种：
\[p_x=a_x-a_{x-1}\\
a_x=a_{x-1}+p_x
\]
所以只要把 \(p\) 数组当作新的原数组，再将这个数组做个前缀和就 OK 了。
区间加法
假设需要将原数列的 \([l,r]\) 全部加上 \(v\)。那么暴力是 \(O(n)\) 的，考虑用差分优化。
公式：\(p_l\gets p_l+v,p_{r+1}\gets p_{r+1}-v\)。
证明：
显然 \(\forall 1\le i\le l-1\)，\(p_i\) 是不变的。那么考虑转化的本质。
我们设 \(s_i\) 表示修改后的数组。即 \(s_i=s_{i-1}+p_i\)。
\[\forall l\le i\le r\\
s_i=\sum_{j=1}^{i}p_j\\
s_i=\sum_{j=1}^{i-1}p_j+p_i\\
s_i=s_{i-1}+p_j
\]
那么在 \([l,r]\) 区间里的数，在前缀和时就会被 \(s_l\) 加上 \(v\)。而 \([r+1,n]\) 里的数（不动的），则在 \(s_{r+1}\) 时减回来了，故值不变。
差分大概也就用到这些，再复杂点的就用线段树吧。
例题
给道例题：NOIP 2012 提高组 借教室。
代码：（差分+二分，时间复杂度 \(O(n\log m)\)）
#include<bits/stdc++.h>
using namespace std;
typedef long long ljl;
const int N=1e6+5;
int n,m;
ljl a[N],tp[N],sum[N],p[N];
struct R{int s,t;ljl d;
}r[N];
void addlr(int l,int r,int v)
{p[l]+=v;p[r+1]-=v;return;
}
bool check(int x)//check [1,x]
{for(int i=1;i<=n;++i)p[i]=tp[i];for(int i=1;i<=x;++i)addlr(r[i].s,r[i].t,-r[i].d);memset(sum,0,sizeof(sum));for(int i=1;i<=n;++i)sum[i]=p[i]+sum[i-1];for(int i=1;i<=n;++i)if(sum[i]<0)return 0;return 1;
}
int main(){ios::sync_with_stdio(0);cin>>n>>m;for(int i=1;i<=n;++i)cin>>a[i];for(int i=1;i<=m;++i)cin>>r[i].d>>r[i].s>>r[i].t;for(int i=1;i<=n;++i)tp[i]=a[i]-a[i-1];int l=0,r=m,mid=0;while(l<r){mid=(l+r+1)>>1;
// cout<<l<<' '<<r<<' '<<mid<<' '<<check(mid)<<'\n';if(check(mid))l=mid;else r=mid-1;}if(l==m){cout<<"0\n";return 0;}cout<<"-1\n"<<l+1<<'\n';return 0;
}