当前位置: 首页 > news >正文

二维前缀和:高效求解矩阵区域和问题

在处理二维矩阵时,频繁计算某一子矩阵的和是一个常见的操作。传统的做法是直接遍历该子矩阵,时间复杂度较高。当矩阵非常大且有大量的查询时,直接计算将变得低效。为了提高效率,我们可以通过 二维前缀和 技巧在常数时间内解决这个问题。

本文将通过一个具体的 Java 实现,介绍如何使用二维前缀和优化子矩阵求和问题。

关键是二维前缀和数组的构造,以及求解区域和的代码部分

测试链接:https://leetcode.cn/problems/range-sum-query-2d-immutable/

一、前缀和的概念

前缀和是解决区间和问题的经典技巧。在一维数组中,前缀和数组 prefixSum 用于存储从数组开头到当前位置的累加和,这样我们可以在 O(1) 时间内查询任意区间 [l, r] 的和。

二维前缀和的思想类似,它在二维矩阵上扩展了前缀和的概念。给定一个 m x n 的矩阵 matrix,二维前缀和数组 sum 中的元素 sum[i][j] 表示从左上角 (0, 0)(i-1, j-1) 的所有矩阵元素的和。通过构造这个前缀和数组,我们能够在常数时间内查询任意子矩阵的元素和。

二、二维前缀和的计算

2.1 二维前缀和的构建

对于一个 m x n 的矩阵 matrix,我们定义一个同样大小的前缀和数组 sum,其中 sum[i][j] 表示从 (0, 0)(i-1, j-1) 的矩阵元素和。构造 sum[i][j] 的公式如下:

sum[i][j] = matrix[i-1][j-1] + sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1]
  • matrix[i-1][j-1]:当前矩阵元素。
  • sum[i-1][j]:上方区域的和。
  • sum[i][j-1]:左侧区域的和。
  • sum[i-1][j-1]:左上角区域重复计算的部分,需要减去。

这样通过累加计算每个位置的前缀和,最终可以在常数时间内求出任意子矩阵的和。

2.2 子矩阵和的查询

通过上述方式构造的二维前缀和数组,可以快速计算任意子矩阵的元素和。给定一个矩阵区域的左上角 (row1, col1) 和右下角 (row2, col2),其和可以通过以下公式计算:

sumRegion(row1, col1, row2, col2) = sum[row2+1][col2+1]- sum[row1][col2+1]- sum[row2+1][col1]+ sum[row1][col1]

三、Java 实现

以下是使用二维前缀和优化矩阵区域和查询的 Java 实现。我们将使用 NumMatrix 类来实现:

public class NumMatrix {private int[][] sum;// 构造函数:计算二维前缀和public NumMatrix(int[][] matrix) {int n = matrix.length;int m = matrix[0].length;sum = new int[n + 1][m + 1];  // 创建一个多出一行一列的前缀和数组// 填充前缀和数组for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {sum[i][j] = matrix[i - 1][j - 1] + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];}}}// 查询子矩阵的和public int sumRegion(int row1, int col1, int row2, int col2) {row1++;col1++;row2++;col2++;return sum[row2][col2] - sum[row1 - 1][col2] - sum[row2][col1 - 1] + sum[row1 - 1][col1 - 1];}public static void main(String[] args) {// 示例矩阵int[][] matrix = {{3, 2, 1, 4},{1, 5, 3, 2},{4, 2, 2, 1},{7, 4, 3, 5}};// 创建 NumMatrix 对象NumMatrix numMatrix = new NumMatrix(matrix);// 查询子矩阵 (1,1) 到 (2,2) 的和System.out.println(numMatrix.sumRegion(1, 1, 2, 2));  // 输出:15}
}
3.1 代码分析
  1. 构造函数NumMatrix(int[][] matrix) 用来构造二维前缀和数组 sum。首先,构造一个大小为 (n+1) x (m+1) 的数组,额外的行和列用于处理边界问题。然后通过双重循环填充 sum 数组,利用之前的公式逐步计算前缀和。

  2. sumRegion 方法sumRegion(int row1, int col1, int row2, int col2) 用于查询子矩阵 (row1, col1)(row2, col2) 的和。通过前缀和的计算公式,能够在常数时间内返回结果。

  3. 主函数:在 main 方法中,我们定义了一个 matrix,并创建了 NumMatrix 对象来处理前缀和的计算。然后调用 sumRegion 方法查询从 (1,1)(2,2) 的子矩阵和,输出为 15

四、时间复杂度

  • 前缀和数组的构造:构造二维前缀和数组的时间复杂度是 O(m * n),其中 mn 分别是矩阵的行数和列数。
  • 查询子矩阵和:查询的时间复杂度是 O(1),因为我们只需要做常数次的数组访问和加减操作。

五、应用场景

二维前缀和特别适用于以下场景:

  1. 静态矩阵区域求和:如果我们需要对矩阵中多个子矩阵进行求和,二维前缀和能够显著减少查询时间。
  2. 优化算法中的区间求和:在一些动态规划或分治算法中,二维前缀和可以高效地处理二维区间和查询。

相关文章:

二维前缀和:高效求解矩阵区域和问题

在处理二维矩阵时&#xff0c;频繁计算某一子矩阵的和是一个常见的操作。传统的做法是直接遍历该子矩阵&#xff0c;时间复杂度较高。当矩阵非常大且有大量的查询时&#xff0c;直接计算将变得低效。为了提高效率&#xff0c;我们可以通过 二维前缀和 技巧在常数时间内解决这个…...

鸢尾花书《编程不难》02---学习书本里面的三个案例

文章目录 1.引言2.第一个例子---模拟硬币的投掷结果3.第二个例子---混合两个一元高斯分布的随机数4.第三个例子---线性回归的作图5.关于书中的问题的解决方案 1.引言 今天的这个文章主要是阅读学习鸢尾花书系列的第一本《编程不难》&#xff0c;今天主要是记录下书里面的两个例…...

MySQL(高级特性篇) 13 章——事务基础知识

一、数据库事务概述 事务是数据库区别于文件系统的重要特性之一 &#xff08;1&#xff09;存储引擎支持情况 SHOW ENGINES命令来查看当前MySQL支持的存储引擎都有哪些&#xff0c;以及这些存储引擎是否支持事务能看出在MySQL中&#xff0c;只有InnoDB是支持事务的 &#x…...

CSS Display属性完全指南

CSS Display属性完全指南 引言核心概念常用display值详解1. block&#xff08;块级元素&#xff09;2. inline&#xff08;行内元素&#xff09;3. inline-block&#xff08;行内块级元素&#xff09;4. flex&#xff08;弹性布局&#xff09;5. grid&#xff08;网格布局&…...

【机器学习篇】K-Means 算法详解:从理论到实践的全面解析

网罗开发 &#xff08;小红书、快手、视频号同名&#xff09; 大家好&#xff0c;我是 展菲&#xff0c;目前在上市企业从事人工智能项目研发管理工作&#xff0c;平时热衷于分享各种编程领域的软硬技能知识以及前沿技术&#xff0c;包括iOS、前端、Harmony OS、Java、Python等…...

IntelliJ IDEA远程开发代理远程服务器端口(免费内网穿透)

IntelliJ IDEA远程开发代理远程服务器端口&#xff08;免费内网穿透&#xff09;&#xff08;JetBrains家的其他IDE应该也支持&#xff09; 之前看到宇宙第一IDE VS Code好像默认代理了远程的端口&#xff0c;但是一直没找到IDEA的同类功能&#xff0c;这次终于发现了 以Intell…...

内核定时器3-用户空间定时器

用户空间定时器与内核定时器的关系 虽然用户空间定时器和内核定时器在实现上各自独立&#xff0c;但用户空间定时器通常依赖于内核定时器提供的基础设施。以下是具体关系&#xff1a; 依赖性 用户空间定时器的实现基于内核定时器。 例如&#xff0c;POSIX 定时器使用内核的 h…...

C++ 字面量深度解析:从基础到实战进阶

在 C 开发中&#xff0c;字面量&#xff08;Literal&#xff09;不仅是基础语法的一部分&#xff0c;更是提升代码可读性、安全性和性能的关键工具。本文将深入探讨 C 字面量的高级特性、最新标准支持&#xff08;C11/14/17/20&#xff09;以及实际开发中的应用技巧&#xff0c…...

论文paper(更新...)

目录 是否rebuttal&#xff1f;rebuttal 技巧 是否rebuttal&#xff1f; 如果不rebuttal 肯定会拒稿&#xff0c;编辑也会给审稿人发信息&#xff0c;如下&#xff1a; Comment: Thanks for your efforts in reviewing this paper. The authors have neither submitted a rebu…...

变形金刚多元宇宙

1 涉及的公司 1.1 孩之宝HasBro 孩之宝与Takara签订协议后&#xff0c;孩之宝开始使用Takara的专利进行研发。 1.2 日本特佳丽Takara公司 特佳丽Takara Diaclone可变形恐龙的机器人玩具 Microman可变形汽车的机器人玩具 1.3 日本东映TOEI ANIMTION 1.4 美国漫威 为了推广玩具…...

HTTP协议的无状态和无连接

无连接 ①无连接的含义 这里所说的无连接并不是指不连接&#xff0c;客户与服务器之间的HTTP连接是一种一次性连接&#xff0c;它限制每次连接只处理一个请求&#xff0c;当服务器返回本次请求的应答后便立即关闭连接&#xff0c;下次请求再重新建立连接。这种一次性连接主要考…...

ASP.NET代码审计 SQL注入篇(简单记录)

sql注入&#xff0c;全局搜索 Request QueryString ToString() select select * aspx是设计页面&#xff0c;而aspx.cs是类页面&#xff0c;也就是说设计页面用到的类信息在这个页面里面&#xff0c;其实就是把设计和实现分离开来。 源码 using System; using System.Collect…...

毫秒级响应的VoIP中的系统组合推荐

在高并发、低延迟、毫秒级响应的 VoIP 场景中&#xff0c;选择合适的操作系统组合至关重要。以下是针对 Ubuntu linux-lowlatency、CentOS Stream kernel-rt 和 Debian 自定义 PREEMPT_RT 的详细对比及推荐&#xff1a; 1. 系统组合对比 特性Ubuntu linux-lowlatencyCentO…...

w186格障碍诊断系统spring boot设计与实现

&#x1f64a;作者简介&#xff1a;多年一线开发工作经验&#xff0c;原创团队&#xff0c;分享技术代码帮助学生学习&#xff0c;独立完成自己的网站项目。 代码可以查看文章末尾⬇️联系方式获取&#xff0c;记得注明来意哦~&#x1f339;赠送计算机毕业设计600个选题excel文…...

shell -c

个人博客地址&#xff1a;shell -c | 一张假钞的真实世界 shell -c {string}&#xff1a;表示命令从-c后的字符串读取。在需要使用管道或者重定向需要sudo时很有用&#xff0c;如下&#xff1a; $ sudo find ../*/exportFiles -mtime 15 -name "*" | xargs -I {} r…...

(笔记+作业)书生大模型实战营春节卷王班---L1G3000 浦语提示词工程实践

学员闯关手册&#xff1a;https://aicarrier.feishu.cn/wiki/QtJnweAW1iFl8LkoMKGcsUS9nld 课程视频&#xff1a;https://www.bilibili.com/video/BV13U1VYmEUr/ 课程文档&#xff1a;https://github.com/InternLM/Tutorial/tree/camp4/docs/L0/Python 关卡作业&#xff1a;htt…...

文献学习笔记:中风醒脑液(FYTF-919)临床试验解读:有效还是无效?

【中风醒脑液&#xff08;FYTF-919&#xff09;临床试验解读&#xff1a;有效还是无效&#xff1f;】 在发表于 The Lancet &#xff08;2024 年 11 月 30 日&#xff0c;第 404 卷&#xff09;的临床研究《Traditional Chinese medicine FYTF-919 (Zhongfeng Xingnao oral pr…...

Chapter2 Amplifiers, Source followers Cascodes

Chapter2 Amplifiers, Source followers & Cascodes MOS单管根据输入输出, 可分为CS放大器, source follower和cascode 三种结构. Single-transistor amplifiers 这一章学习模拟电路基本单元-单管放大器 单管运放由Common-Source加上DC电流源组成. Avgm*Rds, gm和rds和…...

从0开始使用面对对象C语言搭建一个基于OLED的图形显示框架(绘图设备封装)

目录 图像层的底层抽象——绘图设备抽象 如何抽象一个绘图设备&#xff1f; 桥接绘图设备&#xff0c;特化为OLED设备 题外话&#xff1a;设备的属性&#xff0c;与设计一个相似函数化简的通用办法 使用函数指针来操作设备 总结一下 图像层的底层抽象——绘图设备抽象 在…...

Android学习19 -- 手搓App

1 前言 之前工作中&#xff0c;很多时候要搞一个简单的app去验证底层功能&#xff0c;Android studio又过于重型&#xff0c;之前用gradle&#xff0c;被版本匹配和下载外网包折腾的堪称噩梦。所以搞app都只有找应用的同事帮忙。一直想知道一些简单的app怎么能手搓一下&#x…...

云启出海,智联未来|阿里云网络「企业出海」系列客户沙龙上海站圆满落地

借阿里云中企出海大会的东风&#xff0c;以**「云启出海&#xff0c;智联未来&#xff5c;打造安全可靠的出海云网络引擎」为主题的阿里云企业出海客户沙龙云网络&安全专场于5.28日下午在上海顺利举办&#xff0c;现场吸引了来自携程、小红书、米哈游、哔哩哔哩、波克城市、…...

【第二十一章 SDIO接口(SDIO)】

第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...

汽车生产虚拟实训中的技能提升与生产优化​

在制造业蓬勃发展的大背景下&#xff0c;虚拟教学实训宛如一颗璀璨的新星&#xff0c;正发挥着不可或缺且日益凸显的关键作用&#xff0c;源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例&#xff0c;汽车生产线上各类…...

linux arm系统烧录

1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 &#xff08;忘了有没有这步了 估计有&#xff09; 刷机程序 和 镜像 就不提供了。要刷的时…...

ElasticSearch搜索引擎之倒排索引及其底层算法

文章目录 一、搜索引擎1、什么是搜索引擎?2、搜索引擎的分类3、常用的搜索引擎4、搜索引擎的特点二、倒排索引1、简介2、为什么倒排索引不用B+树1.创建时间长,文件大。2.其次,树深,IO次数可怕。3.索引可能会失效。4.精准度差。三. 倒排索引四、算法1、Term Index的算法2、 …...

【OSG学习笔记】Day 16: 骨骼动画与蒙皮(osgAnimation)

骨骼动画基础 骨骼动画是 3D 计算机图形中常用的技术&#xff0c;它通过以下两个主要组件实现角色动画。 骨骼系统 (Skeleton)&#xff1a;由层级结构的骨头组成&#xff0c;类似于人体骨骼蒙皮 (Mesh Skinning)&#xff1a;将模型网格顶点绑定到骨骼上&#xff0c;使骨骼移动…...

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据 Power Query 具有大量专门帮助您清理和准备数据以供分析的功能。 您将了解如何简化复杂模型、更改数据类型、重命名对象和透视数据。 您还将了解如何分析列&#xff0c;以便知晓哪些列包含有价值的数据&#xff0c;…...

【从零开始学习JVM | 第四篇】类加载器和双亲委派机制(高频面试题)

前言&#xff1a; 双亲委派机制对于面试这块来说非常重要&#xff0c;在实际开发中也是经常遇见需要打破双亲委派的需求&#xff0c;今天我们一起来探索一下什么是双亲委派机制&#xff0c;在此之前我们先介绍一下类的加载器。 目录 ​编辑 前言&#xff1a; 类加载器 1. …...

libfmt: 现代C++的格式化工具库介绍与酷炫功能

libfmt: 现代C的格式化工具库介绍与酷炫功能 libfmt 是一个开源的C格式化库&#xff0c;提供了高效、安全的文本格式化功能&#xff0c;是C20中引入的std::format的基础实现。它比传统的printf和iostream更安全、更灵活、性能更好。 基本介绍 主要特点 类型安全&#xff1a…...

离线语音识别方案分析

随着人工智能技术的不断发展&#xff0c;语音识别技术也得到了广泛的应用&#xff0c;从智能家居到车载系统&#xff0c;语音识别正在改变我们与设备的交互方式。尤其是离线语音识别&#xff0c;由于其在没有网络连接的情况下仍然能提供稳定、准确的语音处理能力&#xff0c;广…...