二维差分算法详解

这篇具有很好参考价值的文章主要介绍了二维差分算法详解。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

牛客测试链接

二维差分模板

问题描述

给定一个n行m列的矩阵,下标从1开始。接下来有q次操作,每次操作输入5个参数x1, y1, x2, y2, k,表示把以(x1, y1)为左上角,(x2,y2)为右下角的子矩阵的每个元素都加上k。请输出操作后的矩阵。

输入描述

第一行包含三个整数n,m,q。接下来n行,每行m个整数,代表矩阵的元素。接下来q行,每行5个整数x1, y1, x2, y2, k,分别代表这次操作的参数。

输出描述

输出n行,每行m个数,每个数用空格分开,表示这个矩阵。

算法思路

二维差分算法是一种用于解决矩阵区间更新问题的高效算法。它通过预处理和差分数组的方式,将区间更新的时间复杂度从O(nm)降低到O(1)。

具体步骤如下:

  1. 定义一个大小为(n+1)*(m+1)的差分数组diff,用于存储每个位置的差分值。
  2. 遍历矩阵的每个元素,将其加到差分数组对应位置上。
  3. 对差分数组进行预处理,计算每个位置的前缀和,即diff[i][j]表示原矩阵中(1,1)到(i,j)位置的元素和。
  4. 对每次操作,将对应区间的四个角的差分值进行更新,即diff[a][b] += k, diff[c+1][d+1] += k, diff[c+1][b] -= k, diff[a][d+1] -= k。
  5. 对差分数组进行再次预处理,计算每个位置的前缀和,即diff[i][j]表示操作后的矩阵中(1,1)到(i,j)位置的元素和。
  6. 输出操作后的矩阵。

代码实现

import java.util.Scanner;
import java.io.*;

public class Main {
    static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
    static StreamTokenizer sr = new StreamTokenizer(in);
    static int MAXN = 1005;
    static int n, m, q;
    static long[][] diff = new long[MAXN][MAXN];
    
    static void build() {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                diff[i][j] += diff[i - 1][j] + diff[i][j - 1] - diff[i - 1][j - 1];
            }
        }
    }
    
    static void clear() {
        for (int i = 1; i <= n + 1; i++) {
            for (int j = 1; j <= m + 1; j++) {
                diff[i][j] = 0;
            }
        }
    }
    
    static void add(int a, int b, int c, int d, int k) {
        diff[a][b] += k;
        diff[c + 1][d + 1] += k;
        diff[c + 1][b] -= k;
        diff[a][d + 1] -= k;
    }
    
    static int nextInt() throws IOException {
        sr.nextToken();
        return (int)sr.nval;
    }
    
    public static void main(String[] args) throws IOException {
        n = nextInt();
        m = nextInt();
        q = nextInt();
        
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                add(i, j, i, j, nextInt());
            }
        }
        
        while (q-- > 0) {
            int a = nextInt();
            int b = nextInt();
            int c = nextInt();
            int d = nextInt();
            int k = nextInt();
            add(a, b, c, d, k);
        }
        
        build();
        
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                out.print(diff[i][j] + " ");
            }
            out.println();
            out.flush();
        }
        
        clear();
    }
}

总结

二维差分算法是一种高效解决矩阵区间更新问题的算法。通过预处理和差分数组的方式,可以将区间更新的时间复杂度从O(nm)降低到O(1)。在实际应用中,可以大大提高算法的效率。文章来源地址https://www.toymoban.com/news/detail-806628.html

到了这里,关于二维差分算法详解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • C++ 二维差分 二维前缀和逆运算 差分矩阵

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

    2024年02月21日
    浏览(52)
  • 机器学习中四类进化算法的详解(遗传算法、差分进化算法、协同进化算法、分布估计算法)

    GA算法原理 首先我们来介绍进化算法的先驱遗传算法,遗传算法(Genetic Algorithm,简称GA)是一种最基本的进化算法,它是模拟达尔文生物进化理论的一种优化模型,最早由J.Holland教授于1975年提出。遗传算法中种群分每个个体都是解空间上的一个可行解,通过模拟生物的进化

    2024年02月09日
    浏览(41)
  • 洛谷 P3397 地毯 刷题笔记 二维差分矩阵

    P3397 地毯 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 方法1 欺负数据小  暴力水过 #includeiostream using namespace std; const int N=1010; int a[N][N]; int main(){     int n,m;     cinnm;     for(int i=0;im;i++){         int x1,y1,x2,y2;         cinx1y1x2y2;         for(int q=x1;q=x2;q++){           

    2024年02月03日
    浏览(68)
  • 二维前缀和&二维差分(超详细,python版,其他语言也很轻松能看懂)

    上一篇文章讲解了一维前缀和一维差分,本篇进阶为二维。 二维前缀和跟一维前缀和求法相同,这里直接上例子。 数组a = [[1,2,2,1],[3,2,2,1],[1,1,1,1]] a数组如图: 则数组a的前缀和为:数组b[[1,3,5,6],[4,8,12,14],[5,10,15,18]] b数组如图: 前缀和递推公式为 b[i][j] = b[i - 1][j] + b[i][j - 1]

    2024年04月22日
    浏览(38)
  • 正演(1): 二维声波正演模拟程序(中心差分)Python实现

    目录 1、原理:  1)二维声波波动方程: ​编辑 2)收敛条件(不是很明白) 3)雷克子波 4)二维空间衰减函数  5)边界吸收条件 (不是很明白。。)  2、编程实现 1)参数设置: 2)雷克子波及二维空间衰减函数 3)边界吸收条件 4)波动方程,迭代公式: 5)全部代码如下:

    2024年02月02日
    浏览(41)
  • 【算法详解】力扣240.搜索二维矩阵II

    力扣链接:力扣240.搜索二维矩阵II 编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性: 每行的元素从左到右升序排列。 每列的元素从上到下升序排列。 题目提到该矩阵是从左到右,从上到下递增的,那么我们就要利用这个性质,从矩阵

    2024年01月21日
    浏览(45)
  • 【计算几何】凸多面体重叠判断算法:GJK 算法详解 & C++代码实现二维情形的凸多边形重叠判断

    GJK 算法是由 Gilbert,Johnson,Keerthi 三位前辈发明的, 用来计算两个凸多面体之间的碰撞检测 ,以及最近距离。 GJK 算法可以在 O ( M + N ) O(M+N) O ( M + N ) 的时间复杂度内,检测出碰撞,算法在每次迭代的过程中,都会优先选择靠近原点的方向,因此收敛速度会很快。算法的证明

    2024年02月08日
    浏览(61)
  • 蓝桥杯一维差分 | 算法基础

    ⭐ 简单说两句 ⭐ ✨ 正在努力的小新~ 💖 超级爱分享,分享各种有趣干货! 👩‍💻 提供:模拟面试 | 简历诊断 | 独家简历模板 🌈 感谢关注,关注了你就是我的超级粉丝啦! 🔒 以下内容仅对你可见~ 作者: 后端小知识 , CSDN后端领域新星创作者 |阿里云专家博主 CSDN 个

    2024年02月03日
    浏览(41)
  • 算法之路-------差分数组

    针对数组中连续的大量数据进行修改的问题,如果我们对每个数据都进行依次修改,对于一些少量的数据的修改(例如:1~100这些的),修改的时候我们发现速度貌似还是很快的,但是一旦修改的连续数组中的数量上万了,那么修改的速率就明显下降了。 所以:针对这样的情

    2024年02月06日
    浏览(50)
  • 算法专题:差分数组

    2024年01月18日
    浏览(32)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包