差分算法（一维差分、二维差分）

一、差分的定义

二、一维差分

模版题

题目描述（题目来源于牛客网）

思路

方法一：暴力求解（直接模拟）

代码展示

#include<iostream>

using namespace std;

const int N = 1e5 + 10;
long long a[N];
long long n, m;

int main(){
cin>>n>>m;

//输入数组
for(int i = 1; i<= n; i++){
cin>>a[i];
}

//对区间加k，执行m次
while(m–){
long long l, r, k;
cin>>l>>r>>k;
for(int i = l; i <= r; i++){
a[i] += k;
}
}

//输出全部执行后的数组
for(int i = 1; i <= n; i++){
cout<<a[i]<<" ";
}

return 0;
}

方法二：一维差分数组

图解

图解

代码展示

#include<iostream>

using namespace std;

const int N = 1e5 + 10;
long long a[N], s[N];
long long n, m;

int main(){
//读入整数n,m
cin>>n>>m;

//输入数组
for(int i = 1; i <= n; i++){
cin>>a[i];
}

//计算差分数组
for(int i = 1; i <= n; i++){
s[i] = a[i] – a[i – 1];
}

//处理每一次操作
while(m–){
long long l, r, k;
cin>>l>>r>>k;

//对于每一次操作之后更新差分数组
s[l] += k;
s[r + 1] -= k;
}

//输出处理完全部操作之后的数组
for(int i = 1; i <= n; i++){
a[i] = s[i] + a[i – 1];
cout<< a[i] <<" ";
}

return 0;
}

例题：海底高铁

题目描述（题目来源于洛谷）

思路

代码

#include<iostream>

using namespace std;

const int N = 1e5 + 10;
long long a[N], s[N];
long long n, m;

int main(){
cin>>n>>m;

//读入城市
for(int i = 1; i <= m; i++){
cin>>a[i];
}

//计算差分数组
for(int i = 1; i < m; i++){
//遍历每一个城市—l表示起点，r表示终点，对区间[l,r]之间数加1
if(a[i] < a[i + 1]){
long long l = a[i];
long long r = a[i + 1];
s[l] += 1;
s[r] -= 1;
}else{
long long l = a[i + 1];
long long r = a[i];
s[l] += 1;
s[r] -= 1;
}
}

// 将差分数组转换为每段铁路的实际次数（前缀和）
long long sum = 0;
for(int i = 1; i < n; i++){ // 只处理前 n-1 段铁路
sum += s[i];
s[i] = sum;
}

long long res = 0;
//计算最小花费
for(int i = 1; i < n; i++){
long long a,b,c;
cin>>a>>b>>c;
res += min(a * s[i], c + b * s[i]);
}
cout<<res<<endl;
return 0;
}

三、二维差分

模版题

题目描述（题目来源于牛客网）

思路

代码

#include<iostream>

using namespace std;

const int N = 1e3 + 10;
long long a[N][N], s[N][N];
long long n, m, q;

int main(){
cin>>n>>m>>q;

//输入矩阵
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
cin>>a[i][j];
}
}

//初始化差分数组
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
s[i][j] = a[i][j] – a[i – 1][j] – a[i][j – 1] + a[i – 1][j – 1];
}
}

//对于每一次加k操作，更新差分数组
while(q–){
long long x1, y1, x2, y2, k;
cin>> x1 >> y1 >> x2 >> y2 >> k;

//更新差分数组
s[x1][y1] += k;
s[x1][y2 + 1] -= k;
s[x2 + 1][y1] -= k;
s[x2 + 1][y2 + 1] += k;

}

//还原a数组（计算前缀和）
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
a[i][j] = a[i – 1][j] + a[i][j – 1] – a[i – 1][j – 1] + s[i][j];
}
}

//输出最后的结果
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
cout<<a[i][j]<<" ";
}
cout<<endl;
}
return 0;
}

例题：地毯

题目描述（题目来源于洛谷）

思路

代码

#include<iostream>

using namespace std;

const int N = 1e3 + 10;
long long a[N][N] = {0}, s[N][N];
long long n, m;

int main(){
cin>>n>>m;

// //输入初始矩阵
// for(int i = 1; i <= n; i++){
// for(int j = 1; j <= n; j++){
// cin>>a[i][j];
// }
// }

//初始化差分数组
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
s[i][j] = a[i][j] – a[i -1][j] – a[i][j – 1] + a[i -1][j – 1];
}
}

//根据每次输入的地毯坐标，更新差分数组
while(m–){
long long x1, y1, x2, y2;
cin>>x1>>y1>>x2>>y2;

//更新差分数组
s[x1][y1] += 1;
s[x1][y2 + 1] -= 1;
s[x2 + 1][y1] -= 1;
s[x2 + 1][y2 + 1] += 1;
}
//根据差分数组还原数组a
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
a[i][j] = a[i – 1][j] + a[i][j – 1] – a[i -1][j -1] + s[i][j];
}
}

//输出矩阵
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
cout<<a[i][j]<<" ";
}
cout<<endl;
}
return 0;
}