在做题中学习(55):一维前缀和模板

【模板】前缀和_牛客题霸_牛客网 (nowcoder.com)

题目解释:

注意:下标从1开始的。

l 和 r就是对这n个整数去取一个区间,例如示例一:

(1,2) 区间 就是算出1 2 4 中 1,2下标对应值的和,1+2 = 3

同理,(2,3)   ->    2 + 4 = 6

解法:前缀和


用来快速求出一段连续区间的和。

做法:

1.来一个dp数组(每个元素都是从[1,i] 位置元素的和):

求法:       dp[i] = dp[i-1] + nums[i]

2.使用前缀和dp

既然要求(l,r) 区间的和,而dp数组已经有dp[r] 和dp[l-1]这一段的值了,所以dp[r] - dp[l-1]就可以算出(l,r)区间的值。 

细节

为什么数组下标要从 1 开始

因为如果说题目的 l 是可以 = 0的,那么求[0,2]   就是dp[2] - dp[-1]了,而下标怎么能为负数呢,所以此时需要单独处理判断,而下标从1开始的话,l最小 = 1 [1,2],就是  dp[2] - dp[0] 了,此时只需要让dp[0] = 0就可以了。

#include <iostream>
#include <vector>
using namespace std;int main() 
{//1.把值输入到原始数组int n = 0,q = 0;cin >> n >> q;vector<int> arr(n+1);for(int i = 1;i<=n;i++)cin >> arr[i];//2.构建dp数组vector<long long int> dp(n+1);for(int i = 1;i<=n;i++)dp[i] = dp[i-1] + arr[i];//3.使用dp数组int l = 0,r = 0;while(q--){cin >> l >> r;cout << dp[r] - dp[l-1] <<endl;}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://xiahunao.cn/news/3031791.html

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

SHAP分析+立方样条拟合的展示可能的交互作用

SHAP分析立方样条的拟合展示可能的交互作用 SHAP分析的另一个特点就是对交互作用的分析&#xff0c;计算交互作用的SHAP值&#xff0c;绘制相关的交互作用图表&#xff0c;但是仅局限于xgboost模型&#xff0c;其它的模型不能单独计算相互作用的SHAP值&#xff0c;也就不能绘制…

React 第二十九章 React 和 Vue 描述页面的区别

面试题&#xff1a;React 和 Vue 是如何描述 UI 界面的&#xff1f;有一些什么样的区别&#xff1f; 标准且浅显的回答&#xff1a; React 中使用的是 JSX&#xff0c;Vue 中使用的是模板来描述界面 前端领域经过长期的发展&#xff0c;目前有两种主流的描述 UI 的方案&#xf…

读写备份寄存器BKP与实时时钟RTC

文章目录 读写备份寄存器接线图代码 RTC实时时钟接线图代码 读写备份寄存器 接线图 即接个3.3v的电源到VBT引脚 代码 代码效果&#xff1a;第一次写入备份寄存器&#xff0c;下载程序后再注释掉&#xff0c;再进行下载&#xff0c;之前写入的数据还会保存在备份寄存器中&am…

QQ无人直播秘籍:24小时自动化短剧,边睡边赚,月入过万实战分享!

在如今经济大环境如此糟糕的时代&#xff0c;寻找一种简单、有效的方式来实现日入1000的梦想成为了许多人的追求。而QQ短剧24小时无人直播项目&#xff0c;则是一个备受瞩目的赚钱机会。借助腾讯官方流量扶持&#xff0c;这个项目不仅能够让创业者轻松入门&#xff0c;还能够实…

新火种AI|正面硬刚OpenAI与谷歌?微软竟然偷偷自研出5000亿参数大模型!

在AI领域&#xff0c;微软公司一直以其独到的创新性和前瞻性而闻名。也正因此&#xff0c;它抢先在AI赛道嗅到商机&#xff0c;并极具预判性的投资了OpenAI&#xff0c;使其成为自己在AI赛道上的最强助力。不过&#xff0c;微软的野心不止于此。 根据The Information 5月6日的…

光耦推荐—高速风筒方案中用到哪些光耦型号

高速风筒是现代生活中常见的电器设备&#xff0c;广泛应用于家庭、商业和工业领域&#xff1b;光耦是一种能够将输入信号转换成输出信号的元器件&#xff0c;其作用在于将电气信号转换成光信号&#xff0c;从而实现电路的隔离和保护&#xff1b;采用光耦可实现对风机转速和温度…

品牌控价前要先了解目标

对渠道中出现的低价链接、窜货链接进行治理的过程&#xff0c;就叫做控价&#xff0c;控价的最终目的是为使这些低价链接下架或者改价&#xff0c;但不是所有品牌都只做打击&#xff0c;便能管控好渠道的&#xff0c;也就是说&#xff0c;控价的方法不能只依靠治理&#xff0c;…

【CTFHub】HTTP 请求方式 302跳转 cookie WP

1.请求方式 打开给出的URL进入一个页面&#xff0c;提示原方法是GET&#xff0c;用CTFHUB方法就能获得flag 思路&#xff1a;抓包&#xff0c;将GET方法改成CTFHUB方法进行重新发送请求&#xff0c;查看响应情况 1.打开代理服务器 2.打开BurpSuite 刷新页面获得拦截 3.发送…

【Centos7 】Centos7yum报错:another app is currently holding the yum lock;解决方案

Centos7 yum报错:another app is currently holding the yum lock;waiting for it to exit 大家好 我是寸铁&#x1f44a; 总结了一篇Centos7 yum报错:another app is currently holding the yum lock;waiting for it to exit✨ 喜欢的小伙伴可以点点关注 &#x1f49d; 报错 解…

【UnityRPG游戏制作】Unity_RPG项目_玩法相关※

&#x1f468;‍&#x1f4bb;个人主页&#xff1a;元宇宙-秩沅 &#x1f468;‍&#x1f4bb; hallo 欢迎 点赞&#x1f44d; 收藏⭐ 留言&#x1f4dd; 加关注✅! &#x1f468;‍&#x1f4bb; 本文由 秩沅 原创 &#x1f468;‍&#x1f4bb; 收录于专栏&#xff1a;就业…

认识下MapReduce

&#x1f50d; 什么是MapReduce&#xff1f; MapReduce是一种分布式计算模型&#xff0c;最初由Google提出&#xff0c;用于处理大规模数据集的并行计算。它将数据处理任务分解成独立的Map和Reduce两个阶段&#xff0c;以实现分布式计算和并行化处理。Map阶段负责将输入数据映…

Web3Tools - 助记词生成

Web3Tools - 助记词生成工具 本文介绍了一个简单的助记词生成工具&#xff0c;使用 React 和 Material-UI 构建。用户可以选择助记词的语言和长度&#xff0c;然后生成随机的助记词并显示在页面上 功能介绍 选择语言和长度&#xff1a; 用户可以在下拉菜单中选择助记词的语言&…

头歌实践教学平台:CG1-v1.0-点和直线的绘制

第1关&#xff1a;OpenGL点的绘制 一. 任务描述 根据下面要求&#xff0c;在右侧修改代码&#xff0c;绘制出预期输出的图片。平台会对你编写的代码进行测试。 1.本关任务 熟悉编程环境&#xff1b; 了解光栅图形显示器的特点&#xff1b; 了解计算机绘图的特点&#xff1b…

vivado 配置存储器支持-Artix-7 配置存储器器件

配置存储器支持 本章主要讲解 Vivado 软件支持的各种非易失性器件存储器。请使用本章作为指南 &#xff0c; 按赛灵思系列、接口、制造商、 密度和数据宽度来为您的应用选择适用的配置存储器器件。 Artix-7 配置存储器器件 下表所示闪存器件支持通过 Vivado 软件对 A…

苹果电脑MAC清理系统空间工具CleanMyMacX4.15.3中文版下载

苹果电脑以其出色的性能、优雅的设计和高效的操作系统而受到许多用户的喜爱。然而&#xff0c;随着时间的推移和使用量的增加&#xff0c;你可能会发现你的Mac开始变得缓慢和响应迟缓。这通常是因为硬盘空间被大量占用&#xff0c;影响了系统的整体性能。幸运的是&#xff0c;有…

maven的安装与配置(超详细)

在Java开发中&#xff0c;配置Maven环境有几个重要的原因&#xff1a; 依赖管理&#xff1a;Maven 是一个强大的依赖管理工具&#xff0c;它能够帮助开发人员轻松地管理项目所需的各种第三方库和组件。通过在项目的 Maven 配置文件&#xff08;pom.xml&#xff09;中定义依赖&…

数据结构与算法学习笔记六-二叉树的顺序存储表示法和实现(C语言)

目录 前言 1.数组和结构体相关的一些知识 1.数组 2.结构体数组 3.递归遍历数组 2.二叉树的顺序存储表示法和实现 1.定义 2.初始化 3.先序遍历二叉树 4.中序遍历二叉树 5.后序遍历二叉树 6.完整代码 前言 二叉树的非递归的表示和实现。 1.数组和结构体相关的一些知…

【C#】 SortedDictionary,查找字典中是否存在给定的关键字

欢迎来到《小5讲堂》 这是《C#》系列文章&#xff0c;每篇文章将以博主理解的角度展开讲解。 温馨提示&#xff1a;博主能力有限&#xff0c;理解水平有限&#xff0c;若有不对之处望指正&#xff01; 目录 背景场景说明红黑树原理判断代码Dictionary知识点相关文章 背景 最近…

六西格玛遇上AI:质量提升进入“快车道”

人工智能&#xff08;AI&#xff09;与六西格玛管理方法——正在慢慢接近我们的视野中&#xff0c;预示着在质量管理中一场改革重大改革将要到来。 AI&#xff0c;作为科技的前沿&#xff0c;正以其强大的数据处理能力和机器学习能力&#xff0c;为质量管理提供全新的视角。它…

将来会是Python、Java、Golang三足鼎立吗?

在开始前我有一些资料&#xff0c;是我根据网友给的问题精心整理了一份「 Java的资料从专业入门到高级教程」&#xff0c; 点个关注在评论区回复“888”之后私信回复“888”&#xff0c;全部无偿共享给大家&#xff01;&#xff01;&#xff01; 软件工程里没有银弹&#xff…