【算法通关指南：算法基础篇】二维差分专题：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;typedeflonglong LL;constint N =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(){int n, m, q; cin >> n >> m >> q;for(int i =1; i <= n; i++){for(int j =1; j <= m; j++){ LL x; cin >> x;// [i, j]为左上⻆，[i, j]为右下⻆的矩阵，统⼀加上 x cacl(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(int i =1; i <= n; i++){for(int j =1; j <= m; j++) f[i][j]+= f[i -1][j]+ f[i][j -1]- f[i -1][j -1];}for(int i =1; i <= n; i++){for(int j =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;constint N =1010;int a[N][N];// 差分矩阵 voidcacl(int x1,int y1,int x2,int y2){ a[x1][y1]++; a[x1][y2 +1]--; a[x2 +1][y1]--; a[x2 +1][y2 +1]++;}intmain(){int n, m; cin >> n >> m;while(m--){int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;cacl(x1, y1, x2, y2);}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];}for(int i =1; i <= n; i++){for(int j =1; j <= n; j++) cout << a[i][j]<<" "; cout << endl;}return0;}总结与每日励志
✨ 本文介绍了二维差分算法的原理和应用。二维差分通过在特定位置标记增量，可以高效处理子矩阵元素的批量修改。文章通过两道经典算法题（模板差分和地毯问题）展示了二维差分的实现方法，提供了完整的代码示例。核心思想是利用差分矩阵的性质，通过前缀和还原原始数组。算法简洁高效，适用于大规模矩阵操作。作者鼓励读者坚持学习，相信付出终有回报。
