一维数组差分
我们给定一个数组a[2,4 ,6 ,8 ,10],
则它的差分数组b[2,2,2,2,2,2]
假设我们让数组区间[2,4]元素都增加1
则数组a[2,5,7,9,10]
差分数组b[2,3,2,2,1]
我们可以发现规律，
对于差分数组b，对于任意区间[l,r],增加x
它的数组变化为b[l]+=x, b[r+1]-=x
;
下面这个题目是蓝桥杯的一道差分题目：
https://www.lanqiao.cn/problems/1276/learning/
小明的彩灯
题目描述
小明拥有 NN个彩灯，第 i 个彩灯的初始亮度为 ai 。
小明将进行 Q次操作，每次操作可选择一段区间，并使区间内彩灯的亮度 +x（x 可能为负数）。求 Q 次操作后每个彩灯的亮度（若彩灯亮度为负数则输出 0）。
输入描述
第一行包含两个正整数 N，Q，分别表示彩灯的数量和操作的次数。第二行包含 N 个整数，表示彩灯的初始亮度。接下来 Q 行每行包含一个操作，格式如下：l ，r， x，表示将区间 [l∼r ]的彩灯的亮度 +x。
输出描述
输出共 1 行，包含 N 个整数，表示每个彩灯的亮度。
输入
5 3
2 2 2 1 5
1 3 3
4 5 5
1 1 -100
输出
0 5 5 6 10
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 0x7fffffff
ll a[500005];
ll b[500005];//差分数组
int main()
{
int n,q;
cin>>n>>q;
for(int i=1;i<=n;i++){
cin>>a[i];
b[i]=a[i]-a[i-1];
}
while(q--){
int l,r,x;
cin>>l>>r>>x;
b[l]+=x;
b[r+1]-=x;
}
for(int i=1;i<=n;i++){
a[i]=a[i-1]+b[i];
}
for(int i=1;i<=n;i++){
if(a[i]<=0)
cout<<'0'<<" ";
else
cout<<a[i]<<" ";
}
cout<<endl;
return 0;
}
二维差分数组
类比一维差分，我们执行以下操作
来使被选中的子矩阵中的每个元素的值加上c
b[x1][y1] + = c;
b[x1,][y2+1] – = c;
b[x2+1][y1] – = c;
b[x2+1][y2+1] + = c;
每次对b数组执行以上操作，等价于：
for(int i=x1;i<=x2;i++)
for(int j=y1;j<=y2;j++)
a[i][j]+=c;