二维前缀和、二维差分

二维前缀和

二维前缀和可以快速查询二维数组任何范围上的元素累加和。
如下图红色区域总和为：10

我们就可以使用二维前缀和得到。
下面先讲使用方法：

• 先将原数组复制一份
• 对每一个元素进行遍历，将遍历到的元素=（元素的左边一个元素）加（上面一个元素）减去（左上角的一个元素）加上（元素自己本身）。如图：
• 即”左加上加左上减，加自己“
  
• 那么如果我们想得到红色框里面的元素总和，我们只需要用新数组(下图)的绿色-蓝色1-蓝色2+紫色
• 12-1-2+0=9
  
  那么原理呢？下图：（容斥原理）
  新数组中的元素代表什么呢？从左上角到元素的区域累加和。
  我们的数组按箭头顺序遍历，那么遍历到了问号的时候，前面的部分数组都已经是更改后的了，
  那么上述式子则表示绿色区域总和-蓝色区域1总和-蓝色区域2总和+重复的紫色区域总和，结果等于红色区域的总和
  

总结性笔记

目前是预处理出一个结构，以后每次查询二维数组任何范围上的累加和都是O(1)的操作
1.根据原始状况，生成二维前缀和数组sum，

• sum[i][j]:代表左上角(0，0)到右下角(i，j)这个范围的累加和
• sum[i][j]+=sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1];
• 即”左加上加左上减，加自己“
  2.查询左上角(a,b)到右下角(c,d)这个范围的累加和
• sum[c][d]-sum[c][b-1]-sum[a-1][d]+sum[a-1][b-1];
  3.实际过程中往往补第0行，第0列来减少很多条件判断,当然也可以不补，根据个人习惯决定。

二维差分

二维差分可以批量的快速对任意范围内的元素进行加减操作，
在理解了二维前缀和以后，很容易就能明白二维差分。
例如对红色区域进行+v操作，我们只需要进行下图操作：

再进行前缀和操作，就能得到批量操作以后的新数组。

总结性笔记

在二维数组中，如果经历如下的过程
1.批量的做如下的操作，每个操作都有独立的a、b、c、d、v

• 左上角(a,b)到右下角(c,d)范围上，每个数字+v,怎么快速处理？
  代码实现：

  void add(int a,int b,int c,int d,int v){
  	diff[a][b]+=v;
  	diff[c+1][b]-=v;
  	diff[a][d+1]-=v;
  	diff[c+1][d+1]+=v;

  2.操作做完之后，如何正确得到二维数组中的每个位置的值？
  用前缀和的方式，代码实现：(左加上加左上减，加自己)

  void build(){
  	for(int i=1;i<=n;i++){
  		for(int j=1;j<=n;j++){
  			diff[i][j]+=diff[i-1][j]+diff[i][j-1]-diff[i-1][j-1];
  			}
  		}
  }

  例题

  2025.10.10 P3397 地毯

题目背景

加强版

题目描述

在 $n\times n$ 的格子上有 $m$ 个地毯。

给出这些地毯的信息，问每个点被多少个地毯覆盖。

输入格式

第一行，两个正整数 $n,m$。意义如题所述。

接下来 $m$ 行，每行两个坐标 $(x_1,y_1)$ 和 $(x_2,y_2)$，代表一块地毯，左上角是 $(x_1,y_1)$，右下角是 $(x_2,y_2)$。

输出格式

输出 $n$ 行，每行 $n$ 个正整数。

第 $i$ 行第 $j$ 列的正整数表示 $(i,j)$ 这个格子被多少个地毯覆盖。

输入输出样例 #1

输入 #1

>5 3
>2 2 3 3
>3 3 5 5
>1 2 1 4

输出 #1

>0 1 1 1 0
>0 1 1 0 0
>0 1 2 1 1
>0 0 1 1 1
>0 0 1 1 1

说明/提示

样例解释

覆盖第一个地毯后：

$0$	$0$	$0$	$0$	$0$
$0$	$1$	$1$	$0$	$0$
$0$	$1$	$1$	$0$	$0$
$0$	$0$	$0$	$0$	$0$
$0$	$0$	$0$	$0$	$0$

覆盖第一、二个地毯后：

$0$	$0$	$0$	$0$	$0$
$0$	$1$	$1$	$0$	$0$
$0$	$1$	$2$	$1$	$1$
$0$	$0$	$1$	$1$	$1$
$0$	$0$	$1$	$1$	$1$

覆盖所有地毯后：

$0$	$1$	$1$	$1$	$0$
$0$	$1$	$1$	$0$	$0$
$0$	$1$	$2$	$1$	$1$
$0$	$0$	$1$	$1$	$1$
$0$	$0$	$1$	$1$	$1$

---

数据范围

对于 $20\%$ 的数据，有 $n\le 50$，$m\le 100$。

对于 $100\%$ 的数据，有 $n,m\le 1000$。

我的答案

#include<iostream>
using namespace std;
int main(){
int n;
int m;
cin>>n>>m;
int arr[1002][1002]={0};
for(int i =0;i<m;i++){
int x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;
arr[x1][y1]++;
arr[x1][y2+1]--;
arr[x2+1][y1]--;
arr[x2+1][y2+1]++;
}
for(int i=1;i<n+1;i++){
for(int j=1;j<n+1;j++){
arr[i][j]+=arr[i][j-1]+arr[i-1][j]-arr[i-1][j-1];
cout<<arr[i][j]<<" ";
}
cout<<endl;
}
return 0;
}

制作不易，如果觉得可以，可以在评论区留下你的足迹，嘻嘻~

视频推荐：左程云二维前缀和、二维差分、离散化技巧