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

【算法小课堂】深入理解前缀和算法

在这里插入图片描述

  • 前缀和是指某序列的前n项和,可以把它理解为数学上的数列的前n项和,而差分可以看成前缀和的逆运算。合理的使用前缀和与差分,可以将某些复杂的问题简单化。

我们通过一个例子来理解前缀和算法的优势:

一维前缀和:

www.nowcoder.com

我们可以通过暴力的解法去解决这个问题,但是这样时间复杂度会比较高,达到O(n*q)

我们可以对暴力解法进行优化:

我们以【1,4,7,2,5,8,3,6,9】这个数组来讲解前缀和(快速求出数组中某个连续区间的元素和)这个算法

index为数组下标,至于为什么下标从一开始后面会讲!!!

img

我们提前弄一个前缀和数组dp,这个数组的元素dp【i】代表【1,i】区间内所有元素之和

img

我们在求dp的时候肯定不可以用暴力解法,不然的话时间复杂度又上去了,

dp【i】代表 【1,i】区间内所有元素之和,那dp【i-1】代表 【1,i-1】区间内所有元素之和

  • dp【i】就可以等于dp【i-1】+arr【i】

那我们再来看看题目,题目要求我们输出从l到r区间内所有元素之和

那我们可以直接输出dp【r】-dp【l-1】

#include <iostream>
#include<vector>
using namespace std;
int main() {int n,q;cin>>n>>q;vector<int> arr(n+1);for(int i=1;i<=n;i++) cin>>arr[i];vector<long long> dp(n+1);for(int i=1;i<=n;i++) dp[i]=dp[i-1]+arr[i];while(q--){int l,r;cin>>l>>r;cout<<dp[r]-dp[l-1]<<endl;}return 0;
}
// 64 位输出请用 printf("%lld")

二位前缀和:

首先如果我们使用暴力解法时间复杂度,直接就是O(nmq),我们可以对其使用前缀和算法优化

我们可以创建一个(n+1)(m+1)的的数组arr和(n+1)(m+1)的的前缀和数组dp

  • 这里数组坐标加一也是为了防止越界的情况

dp【i】【j】代表从(1,1)~(i,j)这个区间内所有元素之和

我们如何快速求出dp【i】【j】的值呢?以下面这个数组为例,假设我们要求的是dp【3】【3】

img

我们先来观察一个通用图:我们要求多少A+B+C+D之和

img

A+B+C+D=(A+B)+(A+C)+D-A,括号内的是一个整体

我们可以结合下标的关系推导进一步的关系

img

A+B+C+D=(A+B)+(A+C)+D-A

​ =dp【i-1】【j】+dp【i】【j-1】+arr【i】【j】-dp【i-1】【j-1】

这样我们就求出来了dp的每一个数了,回到题目上,题目要求我们输出(x1,y1)~(x2,y2)这个区间内的所有元素之和,假设让我们输出是是这个区间

img编辑

  • D=(A+B+C+D)-(A+B)-(A+C)+A

img编辑

D=(A+B+C+D)-(A+B)-(A+C)+A

= dp【x2】【y2】-dp【x1-1】【y2】-dp【x2】【y1-1】+dp【x1-1】【y1-1】

为了防止越界,我们开辟数组也要多开一行一列

img

相关文章:

【算法小课堂】深入理解前缀和算法

前缀和是指某序列的前n项和&#xff0c;可以把它理解为数学上的数列的前n项和&#xff0c;而差分可以看成前缀和的逆运算。合理的使用前缀和与差分&#xff0c;可以将某些复杂的问题简单化。 我们通过一个例子来理解前缀和算法的优势&#xff1a; 一维前缀和&#xff1a; ww…...

元对象系统功能

元对象系统功能 建立工程 布局页面 布局页面 修改原件名称 建立元对象 函数作为接口 增加一些固定的属性 #------------------------------------------------- # # Project created by QtCreator 2023-10-24T21:54:44 # #----------------------------…...

【2024秋招】小米中间件后端开发一面2023-9-13-base武汉

1 自我介绍 2 快手实习 2.1 讲讲你写的curd启动器&#xff0c;做了哪些工作呢 答&#xff1a; 2.2 网上也有一些开源的curd代码生成器&#xff0c;你为什么需要自研呢&#xff08;重要&#xff09; 答&#xff1a; &#xff08;1&#xff09;这个必须得自研&#xff0c;因…...

SpringMVC Day 01:入门案例

前言 在我们的日常工作和学习中&#xff0c;Web 开发是一个无法回避的重要环节。而在 Java Web 开发领域&#xff0c;SpringMVC 无疑是一个重量级选手。它以其灵活性、强大功能和清晰的 MVC 结构&#xff0c;赢得了大量开发者的青睐。但是&#xff0c;对于初学者来说&#xff…...

docker、docker-compose安装教程,很详细

docker、docker-compose安装教程&#xff0c;很详细 一、卸载旧版1、查看有没有安装过旧版2、停止docker3、删除安装过docker的相关包4、删除docker相关的镜像和容器 二、docker安装1、设置阿里云镜像2、查看所有docker3、安装最新版本4、安装指定版本 三、使用前准备1、启动do…...

源代码转换:Tangible Software Solutions 23.10 Crack

Tangible Software Solutions The Most Accurate and Reliable Source Code Converters Convert between C#, Java, C, Python, & VB, while saving countless hours of painstaking work and valuable time.源代码转换 Key Benefits Saves valuable time Accurate and com…...

SAD notes

ESKF 总结 prediction 更新误差先验 F F F通过3.42来算 得到 这里有点绕的一点是: 误差状态的 F F F牵涉到名义状态, 而名义状态又需要在时间上推进更新 其中, F中的名义状态的推进通过公式3.41得到, (名义状态不考虑误差, 这一点从3.41d, 3.41e可以看出, 误差状态只考虑…...

[SQL开发笔记]BETWEEN操作符:选取介于两个值之间的数据范围内的值

一、功能描述&#xff1a; BETWEEN操作符&#xff1a;选取介于两个值之间的数据范围内的值。这些值可以是数值、文本或者日期。 二、BETWEEN操作符语法详解&#xff1a; BETWEEN操作符语法&#xff1a; SELECT column1, column2,…FROM table_nameWHERE column BETWEEN val…...

Babylonjs学习笔记(三)——创建天空盒

书接上回&#xff0c;这里讨论创建天空盒&#xff01;&#xff01;&#xff01; // 天空盒const envTex CubeTexture.CreateFromPrefilteredData(./env/environmentSpecular.env,scene)scene.environmentTexture envTex;scene.createDefaultSkybox(envTex,true)scene.environ…...

【计算机网络】文件传输协议FTP和SFTP

1. 介绍 SFTP&#xff08;SSH文件传输协议&#xff09;和FTP&#xff08;文件传输协议&#xff09;都是用于在计算机之间传输文件的网络协议。FTP和SFTP都位于OSI模型中的应用层。这两种协议用于文件传输和管理&#xff0c;是应用层协议&#xff0c;因此它们工作在OSI模型的最…...

Python 编程语言的介绍

Python 是一种高级、动态类型的解释型语言。由 Guido van Rossum 于1989年底发明&#xff0c;并在1991年首次发布。Python 的设计哲学强调代码的可读性和简洁的语法&#xff0c;特别是使用缩进来表示代码块&#xff0c;这使得开发者能够用更少的代码表达想法。 基础概念: 语法…...

centos服务器搭建安装Gitlab教程使用教程

1、更新服务器&#xff1a; sudo yum update -y && sudo yum upgrade -y 2、下载Gitlab的RPM包 https://packages.gitlab.com/gitlab/gitlab-cece表示开源el表示centos 选64位el8对应CentOS8 本教程以centos8为例&#xff0c;在服务器中&#xff0c;下载centos8的…...

linux复习笔记02(小滴课堂)

linux下输入输出错误重定向&#xff1a; 输入重定向&#xff1a;< 一个大于号是进行了覆盖。 两个大于号是追加。 输出重定向可以用于以后日志打印。 错误重定向&#xff1a; 错误重定向是不把信息打印到屏幕上而是打印到指定文件中去&#xff1a; 输出重定向其实是用的1…...

AWVS漏洞扫描使用基础与介绍

漏洞扫描的基本概念和原理 漏洞扫描是指通过使用自动化工具和技术来检测和识别计算机系统和网络中可能存在的安全漏洞&#xff0c;用于帮助网络安全运维人员及时获取网络安全态势。漏洞扫描是网络安全中的重要环节&#xff0c;它可以帮助我们发现和修复网络中的安全漏洞&#x…...

Flink 维表关联

1、实时查询维表 实时查询维表是指用户在 Flink 算子中直接访问外部数据库&#xff0c;比如用 MySQL 来进行关联&#xff0c;这种方式是同步方式&#xff0c;数据保证是最新的。但是&#xff0c;当我们的流计算数据过大&#xff0c;会对外 部系统带来巨大的访问压力&#xff0…...

阳光蟹场小程序的盈利模式与思考深度

随着移动互联网的快速发展&#xff0c;小程序成为了各行各业进行数字化转型的重要工具之一。阳光蟹场小程序作为一款专为蟹场管理和销售提供支持的移动&#xff0c;其盈利模式也备受关注。本文将从阳光蟹场小程序的盈利途径、商业模式和对蟹场管理的影响等方面&#xff0c;深入…...

2-Java进阶知识总结-7-UDP-TCP

文章目录 网络编程概述网络编程三要素--IP地址IP地址--概念&#xff08;IP&#xff1a;Internet Protocol&#xff09;IP地址--分类IP地址--特殊的地址&#xff1a;127.0.0.1IP地址获取--DOS命令IP地址获取--InetAddress类 网络编程三要素--端口端口--概念端口号 网络编程三要素…...

C++数据结构X篇_19_排序基本概念及冒泡排序(重点是核心代码,冒泡是稳定的排序)

文章目录 1. 排序基本概念2. 冒泡排序2.1 核心代码2.2 冒泡排序代码2.3 查看冒泡排序的时间消耗2.4 冒泡排序改进版减小时间消耗 1. 排序基本概念 现实生活中排序很重要&#xff0c;例如:淘宝按条件搜索的结果展示等。 概念 排序是计算机内经常进行的一种操作&#xff0c;其目…...

工作:三菱伺服驱动器连接参数及其电机钢性参数配置与调整

工作&#xff1a;三菱伺服驱动器参数及电机钢性参数配置与调整 一、三菱PLC与伺服驱动器连接参数的设置 1. 伺服配置 单个JET伺服从站链接侧占用点数:Rx/Ry占用64点、RWw/RWr占用32点 图中配置了22个JET伺服从站&#xff0c;占用点数:Rx/Ry占用64222048‬点、RWw/RWr占用322…...

企事业单位/公司电脑文件透明加密保护 | 防泄密软件\系统!

推荐——「天锐绿盾电脑文件防泄密系统」 一款全面的企业/公司数据透明加密防泄密系统&#xff0c;旨在从源头上保障数据的安全和使用安全。 PC访问地址&#xff1a; https://isite.baidu.com/site/wjz012xr/2eae091d-1b97-4276-90bc-6757c5dfedee 它具有以下特点&#xff1a…...

AI Agent与Agentic AI:原理、应用、挑战与未来展望

文章目录 一、引言二、AI Agent与Agentic AI的兴起2.1 技术契机与生态成熟2.2 Agent的定义与特征2.3 Agent的发展历程 三、AI Agent的核心技术栈解密3.1 感知模块代码示例&#xff1a;使用Python和OpenCV进行图像识别 3.2 认知与决策模块代码示例&#xff1a;使用OpenAI GPT-3进…...

【机器视觉】单目测距——运动结构恢复

ps&#xff1a;图是随便找的&#xff0c;为了凑个封面 前言 在前面对光流法进行进一步改进&#xff0c;希望将2D光流推广至3D场景流时&#xff0c;发现2D转3D过程中存在尺度歧义问题&#xff0c;需要补全摄像头拍摄图像中缺失的深度信息&#xff0c;否则解空间不收敛&#xf…...

最新SpringBoot+SpringCloud+Nacos微服务框架分享

文章目录 前言一、服务规划二、架构核心1.cloud的pom2.gateway的异常handler3.gateway的filter4、admin的pom5、admin的登录核心 三、code-helper分享总结 前言 最近有个活蛮赶的&#xff0c;根据Excel列的需求预估的工时直接打骨折&#xff0c;不要问我为什么&#xff0c;主要…...

PL0语法,分析器实现!

简介 PL/0 是一种简单的编程语言,通常用于教学编译原理。它的语法结构清晰,功能包括常量定义、变量声明、过程(子程序)定义以及基本的控制结构(如条件语句和循环语句)。 PL/0 语法规范 PL/0 是一种教学用的小型编程语言,由 Niklaus Wirth 设计,用于展示编译原理的核…...

Java入门学习详细版(一)

大家好&#xff0c;Java 学习是一个系统学习的过程&#xff0c;核心原则就是“理论 实践 坚持”&#xff0c;并且需循序渐进&#xff0c;不可过于着急&#xff0c;本篇文章推出的这份详细入门学习资料将带大家从零基础开始&#xff0c;逐步掌握 Java 的核心概念和编程技能。 …...

【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的“no matching...“系列算法协商失败问题

【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的"no matching..."系列算法协商失败问题 摘要&#xff1a; 近期&#xff0c;在使用较新版本的OpenSSH客户端连接老旧SSH服务器时&#xff0c;会遇到 "no matching key exchange method found"​, "n…...

AirSim/Cosys-AirSim 游戏开发(四)外部固定位置监控相机

这个博客介绍了如何通过 settings.json 文件添加一个无人机外的 固定位置监控相机&#xff0c;因为在使用过程中发现 Airsim 对外部监控相机的描述模糊&#xff0c;而 Cosys-Airsim 在官方文档中没有提供外部监控相机设置&#xff0c;最后在源码示例中找到了&#xff0c;所以感…...

搭建DNS域名解析服务器(正向解析资源文件)

正向解析资源文件 1&#xff09;准备工作 服务端及客户端都关闭安全软件 [rootlocalhost ~]# systemctl stop firewalld [rootlocalhost ~]# setenforce 0 2&#xff09;服务端安装软件&#xff1a;bind 1.配置yum源 [rootlocalhost ~]# cat /etc/yum.repos.d/base.repo [Base…...

STM32---外部32.768K晶振(LSE)无法起振问题

晶振是否起振主要就检查两个1、晶振与MCU是否兼容&#xff1b;2、晶振的负载电容是否匹配 目录 一、判断晶振与MCU是否兼容 二、判断负载电容是否匹配 1. 晶振负载电容&#xff08;CL&#xff09;与匹配电容&#xff08;CL1、CL2&#xff09;的关系 2. 如何选择 CL1 和 CL…...

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

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