前缀和代码解析
前缀和是指数组一定范围的数的总和,常见的有两种,一维和二维,我会用两道题来分别解析
一维
DP34 【模板】前缀和
题目:

题目解析:

暴力解法
直接遍历数组,遍历到下标为 l 时,开始进行相加,直到遍历到下标为 r ,最后返回总和.这样做的时间复杂度为: O(n)
public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别//接收数据int n = in.nextInt(),q=in.nextInt();int[] arr = new int[n+1];arr[0]=0;for(int i=1;i<=n;i++){arr[i]=in.nextInt();}while(q>0){int l=in.nextInt(),r=in.nextInt();int sum = 0;for(int i =l;i<=r;i++){sum+=arr[i];}System.out.println(sum);q--;}}
}
虽然代码本身是没有问题的,但是在某些情况下会运行超时

优化
对于前缀和来说,我们可以使用动态规划的部分知识来进行解决,总共分为两步
1.预处理前缀和数组
我们创建一个新的数组,数组的规模和原数组保持一致,如图:

但是在我们求dp数组时,难免会对原数组重复计算,这样会增加代码的耗时,有没有简洁的方法呢?
当然是有的,从dp的获得式中我们可以发现, dp[i] = dp[i-1]+arr[i]
2.使用数组
最后我们就可以返回值, 也就是上文提到的 dp[r]-dp[l-1]
代码
public static void main(String[] args) {Scanner in = new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别//接收数据int n = in.nextInt(),q=in.nextInt();int[] arr = new int[n+1];arr[0] = 0;for(int i=1;i<arr.length;i++){arr[i] = in.nextInt();}//计算动态数组long[] dp = new long[n+1];dp[0] = 0;for(int i=1;i<dp.length;i++){dp[i]=dp[i-1]+arr[i];}//处理结果while(q>0){int l=in.nextInt(),r=in.nextInt();System.out.println(dp[r]-dp[l-1]);q--;}
}
在代码中我们可以看到,我们为数组增加了辅助节点,也就是 arr[0] 和 dp[0] ,那么为什么要增加这个辅助节点呢?或者为什么在使用数组的时候,下标要从1开始计算呢?
因为如果我们没有辅助节点或者从0开始计算,那么当 l (求前缀和的起点) 为 0 时,那么 dp[l-1] 就会越界
运行结果

二维
二维数组也就是矩阵,在计算矩阵的前缀和时,我们需要更注意一些细节
例题: DP35 【模板】二维前缀和

这道题大致与上一道题相似,所以就不进行暴力解法了,直接开始解析

也就是说,这里我们已经得到了用于动态规划的数组 dp ,我们只要再将dp中的值进行计算,就可以得到最后的值了

所以,最后要得出的答案就是 D = dp[x2][y2] -dp[x1-1][y1] -dp[x1][y1-1] +dp[x1-1][y1-1]
代码:
public static void main(String[] args) {Scanner in = new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别//获取数据int n = in.nextInt(),m=in.nextInt(),q=in.nextInt();int[][] arr = new int[n+1][m+1];for(int i=1;i<n+1;i++){for(int j=1;j<m+1;j++){arr[i][j] = in.nextInt();}}//设置动态矩阵long[][] dp = new long[n+1][m+1];for(int i=1;i<n+1;i++){for(int j=1;j<m+1;j++){dp[i][j] = dp[i-1][j]+dp[i][j-1]+arr[i][j]-dp[i-1][j-1];}}//得出答案while(q>0){int x1=in.nextInt(),y1=in.nextInt(),x2=in.nextInt(),y2=in.nextInt();System.out.println(dp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]+dp[x1-1][y1-1]);q--;}
}
运行结果:

相关文章:
前缀和代码解析
前缀和是指数组一定范围的数的总和,常见的有两种,一维和二维,我会用两道题来分别解析 一维 DP34 【模板】前缀和 题目: 题目解析: 暴力解法 直接遍历数组,遍历到下标为 l 时,开始进行相加,直到遍历到下标为 r ,最后返回总和.这样做的时间复杂度为: O(n) public class Main …...
Windows 环境下安装 Anaconda 并配置
安装Anaconda 1. 下载安装包 官网下载:https://www.anaconda.com/download/success 也可以从国内镜像仓库下载: 中国科学技术大学 https://mirrors.ustc.edu.cn/ 清华大学开源软件镜像站 https://mirrors.tuna.tsinghua.edu.cn/ 2. 安装过程 双…...
大模型在尿潴留风险预测及围手术期方案制定中的应用研究
目录 一、引言 1.1 研究背景与意义 1.2 研究目的 1.3 研究方法与数据来源 二、大模型预测尿潴留的原理与方法 2.1 相关大模型介绍 2.2 模型构建与训练 2.3 模型评估指标与验证 三、术前尿潴留风险预测及方案制定 3.1 术前风险因素分析 3.2 大模型预测结果分析 3.3 …...
JavaScript 简单类型与复杂类型
在JavaScript中,根据数据存储的方式不同,变量可以分为两大类:简单类型(也称为基本数据类型或原始类型)和复杂类型(也称为引用数据类型)。理解这两者的区别对于编写高效且无误的代码至关重要。本…...
AI绘画软件Stable Diffusion详解教程(1):Windows系统本地化部署操作方法(专业版)
一、事前准备 1、一台配置不错的电脑,英伟达显卡,20系列起步,建议显存6G起步,安装win10或以上版本,我的显卡是40系列,16G显存,所以跑大部分的模型都比较快; 2、科学上网࿰…...
大白话Vue 双向数据绑定的实现原理与数据劫持技术
咱们来好好唠唠Vue双向数据绑定的实现原理和数据劫持技术,我会用特别通俗的例子给你讲明白。 啥是双向数据绑定 你可以把双向数据绑定想象成一个神奇的“同步器”。在网页里有两部分,一部分是数据,就像你记在小本本上的信息;另一…...
VUE 获取视频时长,无需修改数据库,前提当前查看视频可以得到时长
第一字段处 <el-table-column label"视频时长" align"center"> <template slot-scope"scope"> <span>{{ formatDuration(scope.row.duration) }}</span> </template> </el-ta…...
antv G6绘制流程图
效果图(优点:可以自定义每一条折线的颜色,可以自定义节点的颜色,以及折线的计算样式等): 代码: <!-- 流程图组件 --> <template><div id"container"></div>…...
完美隐藏滚动条方案 (2024 最新验证)
完美隐藏滚动条方案 (2024 最新验证) css /* 全局隐藏竖直滚动条但保留滚动功能 */ html {overflow: -moz-scrollbars-none; /* Firefox 旧版 */scrollbar-width: none; /* Firefox 64 */-ms-overflow-style: none; /* IE/Edge */overflow-y: overlay; …...
单片机的串口(USART)
Tx - 数据的发送引脚,Rx - 数据的接受引脚。 串口的数据帧格式 空闲状态高电平,起始位低电平,数据位有8位校验位,9位校验位,停止位是高电平保持一位或者半位,又或者两位的状态。 8位无校验位传输一个字节…...
实现分布式限流开源项目
以下是10个可以实现分布式限流中间件的开源项目推荐,这些项目基于不同的技术栈,适用于多种应用场景: 1. **Alibaba Sentinel** Sentinel 是阿里巴巴开源的分布式限流中间件,支持多种限流策略(如QPS、并发线程数等…...
递归构建行政区域树(二)
概述 这篇博客中构建出的行政区域树利用element-ui的Tree组件展示出来。 实现 源码位于码云,欢迎点击哦。 项目结构 最后 好久没写基于element-ui的项目了,都有点生疏了。 好了,如果对你有帮助,欢迎点个免费的赞哦。...
AR技术下的电商:虚拟试穿/试用/试戴成新风尚
随着科技的日新月异,增强现实(AR)技术正悄然改变着我们的生活,尤其在电子商务领域,AR技术的融入正掀起一场前所未有的变革。那么,AR技术究竟是何方神圣?它在电商领域又展现出了哪些非凡的应用呢…...
社群团购平台的愿景构建与开源链动2+1模式S2B2C商城小程序应用探索
摘要:在数字经济背景下,社群团购作为一种新兴的商业模式,凭借其独特的互动性和便捷性,展现出巨大的市场潜力。本文旨在探讨社群团购平台愿景的构建策略,并结合开源链动21模式S2B2C商城小程序的应用,为创业者…...
笔记20250225
关于上拉电阻和下拉电阻的作用 原理 上拉电阻:在上拉电阻所连接的导线上,如果外部组件未启用,上拉电阻则“微弱地”将输入电压信号“拉高”。当外部组件未连接时,对输入端来说,外部“看上去”就是高阻抗的,…...
【项目】基于Boost自主实现搜索引擎
🔥 个人主页:大耳朵土土垚 🔥 所属专栏:Linux系统编程 这里将会不定期更新有关Linux的内容,欢迎大家点赞,收藏,评论🥳🥳🎉🎉🎉 文章目…...
使用 Open3D 批量渲染并导出固定视角点云截图
一、前言 在三维点云处理与可视化中,固定视角批量生成点云渲染截图是一个常见的需求。例如,想要将同一系列的点云(PCD 文件)在同样的视角下生成序列图片,以便后续合成为视频或进行其他可视化演示。本文将介绍如何使用…...
汽车无钥匙进入一键启动操作正确步骤
汽车智能无钥匙进入和一键启动的技术在近年来比较成熟,不同车型的操作步骤可能略有不同,但基本的流程应该是通用的,不会因为时间变化而有大的改变。 移动管家汽车一键启动无钥匙进入系统通常是通过携带钥匙靠近车辆,然后触摸门把…...
JMeter 的基础知识-安装部分
以下将从环境配置开始,为你详细介绍 JMeter 的基础知识,涵盖环境搭建、界面认知、测试计划创建、常用组件使用等方面内容。 1. 环境配置 1.1 安装 Java JMeter 是基于 Java 开发的,所以需要先安装 Java 开发工具包(JDK)。 下载 JDK:访问 Oracle 官方网站(https://www…...
解决后端跨域问题
目录 一、什么是跨域问题? 1、跨域问题的定义 2、举例 3、为什么会有跨域问题的存在? 二、解决跨域问题 1、新建配置类 2、编写代码 三、结语 一、什么是跨域问题? 1、跨域问题的定义 跨域问题(Cross-Origin Resource Sh…...
KubeSphere 容器平台高可用:环境搭建与可视化操作指南
Linux_k8s篇 欢迎来到Linux的世界,看笔记好好学多敲多打,每个人都是大神! 题目:KubeSphere 容器平台高可用:环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...
XML Group端口详解
在XML数据映射过程中,经常需要对数据进行分组聚合操作。例如,当处理包含多个物料明细的XML文件时,可能需要将相同物料号的明细归为一组,或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码,增加了开…...
龙虎榜——20250610
上证指数放量收阴线,个股多数下跌,盘中受消息影响大幅波动。 深证指数放量收阴线形成顶分型,指数短线有调整的需求,大概需要一两天。 2025年6月10日龙虎榜行业方向分析 1. 金融科技 代表标的:御银股份、雄帝科技 驱动…...
智能在线客服平台:数字化时代企业连接用户的 AI 中枢
随着互联网技术的飞速发展,消费者期望能够随时随地与企业进行交流。在线客服平台作为连接企业与客户的重要桥梁,不仅优化了客户体验,还提升了企业的服务效率和市场竞争力。本文将探讨在线客服平台的重要性、技术进展、实际应用,并…...
HTML前端开发:JavaScript 常用事件详解
作为前端开发的核心,JavaScript 事件是用户与网页交互的基础。以下是常见事件的详细说明和用法示例: 1. onclick - 点击事件 当元素被单击时触发(左键点击) button.onclick function() {alert("按钮被点击了!&…...
深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南
🚀 C extern 关键字深度解析:跨文件编程的终极指南 📅 更新时间:2025年6月5日 🏷️ 标签:C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言🔥一、extern 是什么?&…...
华为云Flexus+DeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建
华为云FlexusDeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建 前言 如今大模型其性能出色,华为云 ModelArts Studio_MaaS大模型即服务平台华为云内置了大模型,能助力我们轻松驾驭 DeepSeek-V3/R1,本文中将分享如何…...
如何理解 IP 数据报中的 TTL?
目录 前言理解 前言 面试灵魂一问:说说对 IP 数据报中 TTL 的理解?我们都知道,IP 数据报由首部和数据两部分组成,首部又分为两部分:固定部分和可变部分,共占 20 字节,而即将讨论的 TTL 就位于首…...
Windows安装Miniconda
一、下载 https://www.anaconda.com/download/success 二、安装 三、配置镜像源 Anaconda/Miniconda pip 配置清华镜像源_anaconda配置清华源-CSDN博客 四、常用操作命令 Anaconda/Miniconda 基本操作命令_miniconda创建环境命令-CSDN博客...
苹果AI眼镜:从“工具”到“社交姿态”的范式革命——重新定义AI交互入口的未来机会
在2025年的AI硬件浪潮中,苹果AI眼镜(Apple Glasses)正在引发一场关于“人机交互形态”的深度思考。它并非简单地替代AirPods或Apple Watch,而是开辟了一个全新的、日常可接受的AI入口。其核心价值不在于功能的堆叠,而在于如何通过形态设计打破社交壁垒,成为用户“全天佩戴…...
