免费FanControl：3分钟搞定风扇降噪
2026/9/7 8:04:33
一维差分 & 二维差分 总结+对比+模板+注意事项
核心思想：差分：先修改少数标记点，最后做前缀和把影响扩散到整个区间/矩形；避免暴力循环修改每一个元素，把区间修改从 O(n) 降到 O(1)
一(x_2+1、y_2+1)一维差分
作用
对数组，给区间 ([L,R]) 每个元素加上v a l valval。
只修改2个点，全部修改做完后跑一遍一维前缀和得到原数组。
公式
//差分数组dd[L]+=val;d[(R+1)]-=val;一维差分模板
#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintN=100005;inta[N];intd[N];//差分数组signedmain(){intn,m;cin>>n>>m;for(inti=1;i<=n;i++){cin>>a[i];d[i]=a[i]-a[i-1];//构建差分数组}// m次区间加：[l,r] += valwhile(m--){intl,r,val;cin>>l>>r>>val;d[l]+=val;d[r+1]-=val;}//求前缀和还原原数组for(inti=1;i<=n;i++){a[i]=a[i-1]+d[i];cout<<a[i]<<" ";}return0;}一维差分关键点
- 修改时是
(R+1)，容易越界，数组开大一点 (N+2)。 - 先完成所有差分标记修改，最后统一做前缀和；不能边差分边前缀和。
- 如果原始数组不是全0：
d[i] = a[i] - a[i‑1]初始化差分数组。
二(x_2+1、y_2+1)二维差分
作用
给子矩形：左上角( x 1 , y 1 ) (x_1,y_1)(x1,y1)，右下角( x 2 , y 2 ) (x_2,y_2)(x2,y2)，全部加v a l valval。
只修改4个角点，全部修改完成后跑二维前缀和还原矩阵。
公式
d[x1][y1]+=val;d[x1][y2+1]-=val;d[x2+1][y1]-=val;d[x2+1][y2+1]+=val;二维前缀和还原公式（注意不是差分更新！是还原数组）
a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];二维差分完整模板
#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong#defineendl'\n'constintMAX=2005;inta[MAX][MAX];voidsolve(){intn,m;cin>>n>>m;memset(a,0,sizeofa);while(m--){intx1,y1,x2,y2,val=1;cin>>x1>>y1>>x2>>y2;//二维差分四点更新a[x1][y1]+=val;a[x1][y2+1]-=val;a[x2+1][y1]-=val;a[x2+1][y2+1]+=val;}//二维前缀和扩散，得到真实矩阵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];cout<<a[i][j]<<" ";}cout<<endl;}}signedmain(){ios::sync_with_stdio(0);cin.tie(0);solve();return0;}四(x_2+1、y_2+1)通用重要注意事项（高频踩坑）
数组大小必须+2！
一维：开 (N+2)；二维：开 (MAX+2)防止下标越界。全部差分修改做完，再跑前缀和！
❌错误：改一次差分，立刻跑一次前缀和。
✅正确：把所有区间/矩形全部打完差分标记，最后只跑一遍前缀和扩散。区分两个公式，不要搞混
- 差分更新公式：是用来打标记的（一维2点(x_2+1、y_2+1)二维4点）
- 前缀和公式：是最后用来还原真实数值的，不要把前缀和公式写到循环里面做修改。
- 二维前缀和查询子矩阵和公式（和还原差分的公式不一样！）
求矩形( x 1 , y 1 ) ( x 2 , y 2 ) (x1,y1)~(x2,y2)(x1,y1)(x2,y2)总和：
sum=s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1];注意：这是查询，不是差分，不要和差分四点更新弄混。
- 原始数组不为0时初始化
- 一维差分：
d[i]=a[i]-a[i‑1] - 二维差分：
diff[i][j] = a[i][j]‑a[i‑1][j]‑a[i][j‑1]+a[i‑1][j‑1]；竞赛大部分题目初始全0，不需要。
- 数据范围：二维差分适合矩阵不大，比如2000×2000；如果矩阵是10 5 × 10 5 10^5\times10^5105×105，不能开二维数组，要用扫描线。
五(x_2+1、y_2+1)快速记忆口诀
一维差分：左加，右减一位置减。
二维差分：左上加，右上隔壁减，左下隔壁减，右下隔壁再加回来。
G-Ha~！_河南萌新联赛2026第（二）场：河南农业大学
题意梳理
网格大小固定：2000 × 2000。
一共有n nn只猫猫，每只猫给一个矩形区域[ U i , D i ] [U_i,D_i][Ui,Di]行，[ L i , R i ] [L_i,R_i][Li,Ri]列，代表这只猫哈气覆盖这块矩形。
问题：对于每一个i ii（1 ≤ i ≤ n 1\le i \le n1≤i≤n）：
只关掉第 i 号猫，其他所有猫全部保持开启。求此时网格里有多少个格子，完全没有被任何猫覆盖。
注意：
- 关掉i猫：i猫的矩形直接消失；别的猫不变。
- 格子可以被多只猫重叠覆盖。
- n nn最大2 × 10 5 2\times 10^52×105，但是网格只有2000 × 2000 2000\times20002000×2000，网格很小，猫数量很大。
#include<bits/stdc++.h> using namespace std; #define int long long #define endl '\n' #define pii pair<int,int> #define fi first #define se second const int N=101; const int MAX = 2005; int a[MAX][MAX], b[MAX][MAX]; int u[200005], d[200005], l[200005], r[200005]; void slove(){ int n; cin>>n; for(int i=1;i<=n;i++){ cin>>u[i]>>d[i]>>l[i]>>r[i]; a[u[i]][l[i]]++; a[u[i]][r[i]+1]--; a[d[i]+1][l[i]]--; a[d[i]+1][r[i]+1]++; } int ans=2000*2000; for(int i=1;i<=2000;i++){ for(int j=1;j<=2000;j++){ a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];//这一格被几个哈气猫哈气 if(a[i][j]>=1)ans--; if(a[i][j]==1)b[i][j]=1;//只被一只猫哈气了 else b[i][j]=0;//一直没被哈气 } } //=======【在一个只要是哈气的地方只是其中一只猫哈气的方格图中每个位置的前缀和】 for(int i=1;i<=2000;i++){ for(int j=1;j<=2000;j++){ b[i][j]+=b[i-1][j]+b[i][j-1]-b[i-1][j-1]; } } for(int i=1;i<=n;i++){ int num=b[d[i]][r[i]]-b[d[i]][l[i]-1]-b[u[i]-1][r[i]]+b[u[i]-1][l[i]-1]; cout<<ans+num<<endl; } } signed main(){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int _=1; //cin>>_; while(_--) slove(); return 0; }形象理解
a[x1][y1] ++
从(x1,y1)这个点开始，向右、向下两个方向的所有格子，全部+1。
但是这个影响范围太大了，会蔓延到整张图，我们要把不需要的区域抵消掉。a[x1][y2+1] --
把第x1行，y2+1以及往右的部分，抵消刚才+1的效果。
👉作用：限制本行只能到y2为止。a[x2+1][y1] --
把x2+1行往下全部抵消+1的效果。
👉作用：限制只能到x2行为止。a[x2+1][y2+1] ++
上面②和③两个减号，在点(x2+1,y2+1)位置被减了两次，多减了一次，这里补回来+1。
✨4个点，完成「矩形内部生效，矩形外面不受影响」。
只修改4个位置，不碰矩形中间任何格子；
等全部矩形处理完毕，再跑一遍二维前缀和，把差分的影响扩散开，得到每个格子最终值。
关键疑问：为什么不用区分“这个(a==1)到底是不是i号猫贡献的？”
这里是这道题的巧妙点！
(b[i][j]=1) 的格子，它一定属于且仅属于恰好某一只猫的矩形。
如果一个格子(a=1)，并且这个格子落在 i 的矩形里面 → 那唯一覆盖它的就只能是i猫，不可能是别的猫。
。