前言
上一期我们分享了一维差分的使用方法,这一期我们将接着上期的内容带大家了解二位差分的使用方法,话不多说,LET’S GO!(上一期链接)
二维差分
二维差分我们可以用于对矩阵区间进行多次操作的题。
二维差分我们还可以采用一维差分的思想,如图假如我们要对区间[x1,x2],[y1,y2]的元素都+1:
即:
arrsum[x1][y1] += 1;
arrsum[x1][y2+1] -= 1;
arrsum[x2+1 ][y1] -= 1;
arrsum[x2+1][y2+1] += 1;
思路就是这样,操作完之后直接求数组全缀合就是目标矩阵数组,下面我们上实战。
给出矩阵数组arr,共有n行m列,对其进行t次操作,每次操作会对[ x1 , x2 ],[ y1,y2 ]区间内的元素+1,请输出进行操作后的arr数组。
输入样例
第一行为n,m和q
往后n行为矩阵数组的元素
往后q行为x1,y1,x2,y2
测试样例
3 3 2
1 1 1
1 1 1
1 1 1
1 1 2 2
2 2 3 3
输出样例
2 2 1
2 3 2
1 2 2
题解:文章来源:https://www.toymoban.com/news/detail-769454.html
#include<stdio.h>
int arr[100][100];
int arrsum[100][100];//前缀和数组
int main()
{
int n, m, t;
scanf("%d %d %d", &n, &m, &t);
for (int i = 1; i <= n; i++)//输入数组
{
for (int j = 1; j <= m; j++)
{
scanf("%d", &arr[i][j]);
}
}
for (int i = 1; i <= n; i++)//操作arrsum数组使其前缀和为目标数组
{
for (int j = 1; j <= m; j++)
{
arrsum[i][j] += arr[i][j];
arrsum[i+1][j] -= arr[i][j];
arrsum[i][j+1] -= arr[i][j];
arrsum[i+1][j+1] += arr[i][j];
}
}
while (t--)//t次操作
{
int x1, y1, x2, y2;
scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
arrsum[x1][y1] += 1;
arrsum[x1][y2+1] -= 1;
arrsum[x2+1 ][y1] -= 1;
arrsum[x2+1][y2+1] += 1;
}
for (int i = 1; i <= n; i++)//求前缀和
{
for (int j = 1; j <= m; j++)
{
arrsum[i][j] += arrsum[i-1][j]+arrsum[i][j-1]-arrsum[i-1][j-1];
}
}
for (int i = 1; i <= n; i++)//打印目标数组
{
for (int j = 1; j <= m; j++)
{
printf("%d ", arrsum[i][j]);
}
printf("\n");
}
return 0;
}
尾声
本期分享就到这里,如果觉得博主讲的不错的话请给博主一个关注,点赞,收藏支持一下吧~,博主还将持续分享更多知识,我们下期再见!文章来源地址https://www.toymoban.com/news/detail-769454.html
到了这里,关于二维差分详解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!