【算法通关指南：算法基础篇（四）】二维差分专题：1.【模板】差分 2.地毯

🔥小龙报：个人主页
🎬作者简介：C++研发，嵌入式，机器人方向学习者
❄️个人专栏：《算法通关指南》
✨永远相信美好的事情即将发生

前言

本专栏聚焦算法题实战，系统讲解算法模块：以《c++编程》，《数据结构和算法》《基础算法》《算法实战》 等几个板块以题带点，讲解思路与代码实现，帮助大家快速提升代码能力
ps:本章节题目分两部分，比较基础笔者只附上代码供大家参考，其他的笔者会附上自己的思考和讲解，希望和大家一起努力见证自己的算法成长

一、二维差分

可以类比「⼀维差分数组」的性质，推导出「⼆维差分矩阵」的性质：
• 在差分数组中某个位置标记：表示后续元素统⼀被修改；
• 在差分数组中求前缀和：能够还原出原始数组。
假设我们需要将原始矩阵a中，以（x1,y1）为左上角,(x2,y2)为右下角的子矩阵的每个元素都加上k

结论：
由此可得差分矩阵的性质：
f[x1 ][y1 ]+ = k
f[x1 ][y2 + 1]− = k
f[x2 + 1][y1 ]− = k
f[x2 + 1][y2 + 1]+ = k

二、二维差分经典算法题

2.1【模板】差分

2.1.1题目

链接：【模板】差分

2.1.2 算法原理

依照刚才讲解二维差分原理模拟即可

2.2.3代码

#include<iostream>using namespace std;typedeflonglongLL;constintN=1100;LL f[N][N];voidcacl(LL x1,LL y1,LL x2,LL y2,LL k){f[x1][y1]+=k;f[x1][y2+1]-=k;f[x2+1][y1]-=k;f[x2+1][y2+1]+=k;}intmain(){intn,m,q;cin>>n>>m>>q;for(inti=1;i<=n;i++){for(intj=1;j<=m;j++){LL x;cin>>x;// [i, j]为左上⻆，[i, j]为右下⻆的矩阵，统⼀加上 xcacl(i,j,i,j,x);}}while(q--){LL x1,y1,x2,y2,k;cin>>x1>>y1>>x2>>y2>>k;cacl(x1,y1,x2,y2,k);}for(inti=1;i<=n;i++){for(intj=1;j<=m;j++)f[i][j]+=f[i-1][j]+f[i][j-1]-f[i-1][j-1];}for(inti=1;i<=n;i++){for(intj=1;j<=m;j++)cout<<f[i][j]<<" ";cout<<endl;}return0;}

2.2 地毯

2.2.1题目

链接：地毯

2.2.2 算法原理

直接利⽤二维差分矩阵模拟即可

2.2.3代码

#include<iostream>using namespace std;constintN=1010;inta[N][N];// 差分矩阵voidcacl(intx1,inty1,intx2,inty2){a[x1][y1]++;a[x1][y2+1]--;a[x2+1][y1]--;a[x2+1][y2+1]++;}intmain(){intn,m;cin>>n>>m;while(m--){intx1,y1,x2,y2;cin>>x1>>y1>>x2>>y2;cacl(x1,y1,x2,y2);}for(inti=1;i<=n;i++){for(intj=1;j<=n;j++)a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];}for(inti=1;i<=n;i++){for(intj=1;j<=n;j++)cout<<a[i][j]<<" ";cout<<endl;}return0;}

总结与每日励志

✨本文介绍了二维差分算法的原理和应用。二维差分通过在特定位置标记增量，可以高效处理子矩阵元素的批量修改。文章通过两道经典算法题（模板差分和地毯问题）展示了二维差分的实现方法，提供了完整的代码示例。核心思想是利用差分矩阵的性质，通过前缀和还原原始数组。算法简洁高效，适用于大规模矩阵操作。作者鼓励读者坚持学习，相信付出终有回报。