二维前缀和&二维差分(超详细,python版,其他语言也很轻松能看懂)

这篇具有很好参考价值的文章主要介绍了二维前缀和&二维差分(超详细,python版,其他语言也很轻松能看懂)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

上一篇文章讲解了一维前缀和&一维差分,本篇进阶为二维。

二维前缀和:

二维前缀和跟一维前缀和求法相同,这里直接上例子。
数组a = [[1,2,2,1],[3,2,2,1],[1,1,1,1]]

a数组如图:
二维差分python,python,算法,算法,python,蓝桥杯

则数组a的前缀和为:数组b[[1,3,5,6],[4,8,12,14],[5,10,15,18]]

b数组如图:
二维差分python,python,算法,算法,python,蓝桥杯
前缀和递推公式为 b[i][j] = b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1] + a[i][j],因为i = 0 和 j = 0时,会超出索引范围,所以在定义数组a,b时应该多定义一行0和一列0,如图所示a数组

二维差分python,python,算法,算法,python,蓝桥杯
这样就不会报错,也不需要进行首行和首列的单独定义,更加方便理解和书写。

二维差分:

前文中讲到类似于数学中的求导和积分,差分可以看成前缀和的逆运算。
像上述数组a,b 数组a就是数组b的差分数组。

这里以模板题为准,讲解两种差分方法,一种便于理解,一种就是优化,稍微难理解点,建议大家掌握第一种方法(第二种方法我理解半天才搞懂。。。)先看题。

差分矩阵:

题目链接:差分矩阵
输入一个 n 行 m 列的整数矩阵,再输入 q 个操作,每个操作包含五个整数 x1,y1,x2,y2,c,其中 (x1,y1) 和 (x2,y2) 表示一个子矩阵的左上角坐标和右下角坐标。每个操作都要将选中的子矩阵中的每个元素的值加上 c。
请你将进行完所有操作后的矩阵输出。

输入格式
第一行包含整数 n,m,q。接下来 n 行,每行包含 m 个整数,表示整数矩阵。接下来 q 行,每行包含 5 个整数 x1,y1,x2,y2,c,表示一个操作。

输出格式
共 n 行,每行 m 个整数,表示所有操作进行完毕后的最终矩阵。

数据范围
1≤n,m≤1000,
1≤q≤100000,
1≤x1≤x2≤n,
1≤y1≤y2≤m,
−1000≤c≤1000,
−1000≤矩阵内元素的值≤1000

输入样例:

3 4 3
1 2 2 1
3 2 2 1
1 1 1 1
1 1 2 2 1
1 3 2 3 2
3 1 3 4 1

输出样例:

2 3 4 1
4 3 4 1
2 2 2 2

方法一(很好理解):

因为差分可以看成前缀和的逆运算,可以从矩阵前缀和的构造中反推出差分矩阵。

二维前缀和的递推公式为b[i][j] = b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1] + a[i][j]

这里b是前缀和矩阵,a是差分矩阵。

所以可以反推出a[i][j] = b[i][j] - b[i - 1][j] - b[i][j - 1] + b[i - 1][j - 1]

递推公式有了就可以构造差分矩阵,为了方便理解和书写,定义矩阵时要多定义一行和一列(差分数组要多定义两行两列之后区间加减数时会用到,使之不超出索引范围

差分矩阵有了,如何加减呢?
与一维差分类似,这里给出差分数组的区间图方便大家理解,给出x1,y1,x2,y2,c,要在b[x1][y1] ~ b[x2][y2] 内加c

如图所示:
二维差分python,python,算法,算法,python,蓝桥杯
b[x1][ y1 ] +=c ; 对应下图1 ,让整个a数组中蓝色矩形面积的元素都加上了c。
b[x1,][y2+1]-=c ; 对应图2 ,让整个a数组中绿色矩形面积的元素再减去c,使其内元素不发生改变。
b[x2+1][y1] -=c ; 对应图3 ,让整个a数组中紫色矩形面积的元素再减去c,使其内元素不发生改变。
b[x2+1][y2+1] +=c; 对应图4,让整个a数组中红色矩形面积的元素再加上c,红色内的相当于被减了两次,再加上一次c,才能使其恢复。

二维差分python,python,算法,算法,python,蓝桥杯
这样,我们构造二维差分数组 让原二维数组a中所选中子矩阵中的每一个元素加上c的操作,可以由O(n*n)的时间复杂度优化成O(1)(四次操作)。

之后就用前缀和公式求出新的前缀和矩阵是什么即可。

方法二(优化):

方法二的优化其实也没有优化多少,而且不太好理解,不是很推荐,但毕竟多多少少还是有可取之处。

a[][]数组是b[][]数组的前缀和数组,那么b[][]a[][]的差分数组

原数组: a[i][j]

我们去构造差分数组: b[i][j]

使得a数组中a[i][j]b数组左上角(1,1)到右下角(i,j)所包围矩形元素的和。

如何构造b数组呢?

我们去逆向思考。

同一维差分,我们构造二维差分数组目的是为了 让原二维数组a中所选中子矩阵中的每一个元素加上c的操作,可以由O(n*n)的时间复杂度优化成O(1)

已知原数组a中被选中的子矩阵为 以(x1,y1)为左上角,以(x2,y2)为右下角所围成的矩形区域;

始终要记得,a数组是b数组的前缀和数组,比如对b数组的b[i][j]的修改,会影响到a数组中从a[i][j]及往后的每一个数。

假定我们已经构造好了b数组,类比一维差分,我们执行以下操作
来使被选中的子矩阵中的每个元素的值加上c

b[x1][y1] += c;

b[x1][y2+1] -= c;

b[x2+1][y1] -= c;

b[x2+1][y2+1] += c;

每次对b数组执行以上操作,等价于:
a[i][j]+=c

我们画个图去理解一下这个过程:
二维差分python,python,算法,算法,python,蓝桥杯

b[x1][ y1 ] +=c ; 对应图1 ,让整个a数组中蓝色矩形面积的元素都加上了c。
b[x1,][y2+1]-=c ; 对应图2 ,让整个a数组中绿色矩形面积的元素再减去c,使其内元素不发生改变。
b[x2+1][y1]- =c ; 对应图3 ,让整个a数组中紫色矩形面积的元素再减去c,使其内元素不发生改变。
b[x2+1][y2+1]+=c; 对应图4,让整个a数组中红色矩形面积的元素再加上c,红色内的相当于被减了两次,再加上一次c,才能使其恢复。

二维差分python,python,算法,算法,python,蓝桥杯

方法二的重点就在这,前面一堆废话

我们可以先假想a数组为空,那么b数组一开始也为空,但是实际上a数组并不为空,因此我们每次让b数组以(i,j)为左上角到以(i,j)为右下角面积内元素(其实就是一个小方格的面积)去插入 c=a[i][j],等价于原数组a中(i,j) 到(i,j)范围内 加上了 a[i][j] ,因此执行n*m次插入操作,就成功构建了差分b数组.

这叫做曲线救国。

代码及详细注释:

n, m, c = map(int, input().split())  # 输入三个整数n, m, c

# 初始化二维列表a,将第一行全为0,后续行根据输入的路径更新
a = [[0] * (m + 1)]
for i in range(n):
    path = list(map(int, input().split()))
    path = [0, *path]  # 在每一行的开头插入一个0
    a.append(path)

# 初始化二维列表b,计算每个元素的差分值
b = [[0] * (m + 2) for _ in range(n + 2)]
for i in range(1, n + 1):
    for j in range(1, m + 1):
        b[i][j] = a[i][j] - a[i - 1][j] - a[i][j - 1] + a[i - 1][j - 1]

# 根据输入的操作更新二维列表b的值
for _ in range(c):
    x1, y1, x2, y2, c = map(int, input().split())
    b[x1][y1] += c
    b[x2 + 1][y1] -= c
    b[x1][y2 + 1] -= c
    b[x2 + 1][y2 + 1] += c

# 初始化二维列表res,计算前缀和
# 这里我定义了一个新数组,便于大家理解,节省空间的话也可以在原数组上进行
res = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
    for j in range(1, m + 1):
        res[i][j] = res[i - 1][j] + res[i][j - 1] - res[i - 1][j - 1] + b[i][j]

# 输出最终结果
for i in range(1, n + 1):
    print(" ".join(map(str, res[i][1:])))

总结:

二维前缀和&二维差分也是竞赛经常考的题型,二维差分的重点在于差分数组的构造和区间的加减的,总结起来就两个公式

  1. b[x1][y1] += c;b[x1][y2+1] -= c;b[x2+1][y1] -= c;b[x2+1][y2+1] += c;
  2. a[i][j] = b[i][j] - b[i - 1][j] - b[i][j - 1] + b[i - 1][j - 1]

两篇博客详细讲解了一维和二维的差分和前缀和,并给出了两种方法的模板题文章来源地址https://www.toymoban.com/news/detail-855269.html

到了这里,关于二维前缀和&二维差分(超详细,python版,其他语言也很轻松能看懂)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 前缀和&差分

    前缀和:一段序列里的前n项和 给出n个数,在给出q次问询,每次问询给出L、R,快速求出每组数组中一段L至R区间的和 给出一段数组,每次问询为求出l到r区间的和 普通方法: L到R进行遍历,那么在每次求区间和的过程中时间复杂度为O(n),q次问询时间复杂度为O(q*n) 前缀和:

    2024年02月15日
    浏览(25)
  • 前缀和 差分

    对于数列A,它的前缀和数列S[i]就表示数列A从第一个元素到第i个元素的总和。 前缀和的主要用处:求任意区间的区间和 一般通过遍历求和的时间复杂度是O(n),通过前缀和可以减少为O(1) 具体解法如下: ​前缀和计算区间[l,r]的区间和:S[r] - S[l - 1] ACWing 795前缀和 Tips: ​让元素

    2024年02月05日
    浏览(41)
  • 前缀和、差分

    前缀和可以快速求区间和。 差分相当于前缀和的逆运算。 前缀和、差分都是以空间换时间的算法 注意:本文图文并茂 将提供以下图文链接供大家理解: 图文链接: 飞书图解链接🎉🎉🎉 密码: 672Z172 定义 前缀和可以简单理解为「数列的前 n 项的和」,是一种重要的预处

    2024年02月05日
    浏览(34)
  • 算法基础之差分和前缀和

    结论:差分是前缀和的逆运算 举例 一维差分 二维差分 用在一维子区间里的数都增减一个固定值,把对于区间内每个数的操作转换为对于差分数组中的端点的操作,时间复杂度降为o(1)。 用在二维子矩阵里的数都增减一个固定值,把对于子矩阵的每个数的操作转换为对应差分

    2024年02月07日
    浏览(31)
  • 第四章:前缀和、差分(数列)

    在解释什么是前缀和之前,我们先回顾一下高中学过的数列: 我们这里所说的前缀和其实就是我们在高中学的数列中的 Sn(前n项和) ,只是我们这里需要将 S1 , S2 , S3 , S4 …… Sn 当作一个新的数组。 为了这个式子的高度统一性,我们的S0和a0都是不存储数据的,将其设置为0,这

    2023年04月08日
    浏览(22)
  • 【算法】—前缀和与差分详解

     前缀和指一个数组的某下标之前的所有数组元素的和( 即数列的前n项求和 ),前缀和是一种重要的 预处理 ,能够降低算法的时间复杂度,可以快速地求出某一段的和,对于处理区间之间的问题是往往十分高效 相比较其他算法而言, 前缀和更像是一种解题的技巧,一种优

    2024年02月04日
    浏览(37)
  • 【算法基础】前缀和与差分

    😽 PREFACE 🎁欢迎各位→点赞 👍 + 收藏 ⭐ + 评论 📝 📢系列专栏: 算法 💪 种一棵树最好是十年前其次是现在 前缀和指一个数组的某下标之前的所有数组元素的和(包含其自身)。前缀和分为一维前缀和,以及二维前缀和。前缀和是一种重要的预处理,能够降低算法的时

    2024年01月19日
    浏览(26)
  • 【算法基础2】前缀和与差分

    前缀和是某数列的前n项数的和,而差分则可以看做是前缀和的逆运算。前缀和与差分比起是一种算法,更像是一种解决问题的思路,通过构造一个特殊的数组,就可以让我们将某些复杂的问题简化。 (1)一维前缀和 已知一个数列a[n],用S[n]来表示这个数列的前n项和数列。

    2024年04月14日
    浏览(34)
  • C/C++ 前缀和与差分

    个人主页:仍有未知等待探索_C语言疑难,数据结构,算法-CSDN博客 专题分栏:算法_仍有未知等待探索的博客-CSDN博客 目录 一、前言 1、什么是前缀和 2、什么是差分 3、优势 1.朴素做法: 2.用差分数组 二、代码实现 1、给一个数组去求其差分数组 2、给一个数组去求其前缀和数

    2024年02月03日
    浏览(27)
  • C++基础算法前缀和和差分篇

    📟作者主页:慢热的陕西人 🌴专栏链接:C++算法 📣欢迎各位大佬👍点赞🔥关注🚓收藏,🍉留言 主要讲解了前缀和和差分算法 Ⅵ .Ⅰ前缀和 ① 一维前缀和 : ​ 就是构建一个新的数组 s ,用来存储另一个数组的和前 i 个数组元素的和。用公式表达就是: S [ i ] = a [ 0 ]

    2024年02月16日
    浏览(38)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包