【算法|前缀和系列No.1】牛客网 DP34 【模板】前缀和

个人主页:兜里有颗棉花糖
欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创
收录于专栏【手撕算法系列专栏】【牛客网刷题】
🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助
🍓希望我们一起努力、成长,共同进步。
在这里插入图片描述

点击直接跳转到该题目

目录

  • 1️⃣题目描述
  • 2️⃣题目解析
  • 3️⃣解题代码

1️⃣题目描述

题目描述:
给定一个长度为n的数组a1,a2,…,an
接下来有q次查询, 每次查询有两个参数l, r。
对于每个询问, 请输出al,al+1,…ar

输入描述:
第一行包含两个整数n和q。
第二行包含n个整数, 表示a1,a2,…,an
接下来q行,每行包含两个整数l和r。

1≤n,q≤ 1 0 5 10^{5} 105
- 1 0 9 10^{9} 109 ≤ a[i] ≤ 1 0 9 10^{9} 109
1 ≤ l ≤ r ≤ n

输出描述:
输出q行,每行代表一次查询的结果。

示例:

输出:
3 2
1 2 4
1 2
2 3

2️⃣题目解析

前缀和的思想是通过提前计算和存储每个位置前的元素之和,以便在需要时能够快速获取。通过预先计算并存储前缀和,我们可以在O(1)的时间复杂度内获得任意区间内元素的和,而不需要每次都重新计算。对于前缀和问题的话总共分为两步骤:①创建一个前缀和数组;②使用前缀和数组。

状态表示:

  • dp[i]表示数组从[1,i]之间所有元素的和

状态转移方程:

  • dp[i] = dp[i - 1] + arr[i]

关于本题目的时间复杂度如下:

  • 时间复杂度:O(q) + O(n)O(q)是用来查询q次询问。而O(n)用来创建前缀和数组。

3️⃣解题代码

#include<iostream>
#include<vector>
using namespace std;int main()
{int n,q;cin >> n >> q;vector<long long> arr(n + 1),dp(n + 1);for(int i = 1;i <= n;i++)cin >> arr[i];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;
}

最后就是代码通过啦!!!

在这里插入图片描述

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

如何从 Pod 内访问 Kubernetes 集群的 API

Kubernetes API 是您检查和管理集群操作的途径。您可以使用Kubectl CLI、工具(例如curl)或流行编程语言的官方集成库来使用 API 。 该 API 也可供集群内的应用程序使用。Kubernetes Pod 会自动获得对 API 的访问权限,并且可以使用提供的服务帐户进行身份验证。您可以通过使…

19 | 如何搞清楚事务、连接池的关系?正确配置是怎样的

事务的基本原理 在学习 Spring 的事务之前&#xff0c;你首先要了解数据库的事务原理&#xff0c;我们以 MySQL 5.7 为例&#xff0c;讲解一下数据库事务的基础知识。 我们都知道 当 MySQL 使用 InnoDB 数据库引擎的时候&#xff0c;数据库是对事务有支持的。而事务最主要的作…

Elasticsearch实现检索词自动补全(检索词补全,自动纠错,拼音补全,繁简转换) 包含demo

Elasticsearch实现检索词自动补全 自动补全定义映射字段建立索引测试自动补全 自动纠错查询语句查询结果 拼音补全与繁简转换安装 elasticsearch-analysis-pinyin 插件定义索引与映射建立拼音自动补全索引测试拼音自动补全测试繁简转换自动补全 代码实现demo结构demo获取 自动补…

【c语言】迷宫游戏

之前想写的迷宫游戏今天终于大功告成&#xff0c;解决了随机生成迷宫地图的问题&#xff0c;使用的是深度优先算法递归版本&#xff0c;之前的迷宫找通路问题用的是深度优先算法的非递归实现.之前写过推箱子&#xff0c;推箱子用到了人物的移动&#xff0c;以及碰到墙就不会走&…

【ALO-BP预测】基于蚁狮算法优化BP神经网络回归预测研究(Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…

Python学习----Day08

函数变量的作用域 全局作用域 全局作用域在程序执行时创建&#xff0c;在程序执行结束时销毁。所有函数以外的区域都是全局作用域。在全局作用域中定义的变量&#xff0c;都属于全局变量&#xff0c;全局变量可以在程序的任意位置被访问。 函数作用域 函数作用域在函数调用…

【Eclipse】解决插件下载速度太慢

解决方案&#xff1a;修改镜像 下面列出几个国内的镜像网站&#xff1a; 中国科学技术大学(5.6MB/s) http://mirrors.ustc.edu.cn/eclipse/ 北京理工大学&#xff08;600KB/s&#xff09; http://mirror.bit.edu.cn/eclipse/ 大连东软信息学院(400KB/s) http://mirrors.neuso…

Linux网络编程系列之服务器编程——阻塞IO模型

Linux网络编程系列 &#xff08;够吃&#xff0c;管饱&#xff09; 1、Linux网络编程系列之网络编程基础 2、Linux网络编程系列之TCP协议编程 3、Linux网络编程系列之UDP协议编程 4、Linux网络编程系列之UDP广播 5、Linux网络编程系列之UDP组播 6、Linux网络编程系列之服务器编…

Ubuntu:VS Code IDE安装ESP-IDF【保姆级】

物联网开发学习笔记——目录索引 参考&#xff1a; VS Code官网&#xff1a;Visual Studio Code - Code Editing. Redefined 乐鑫官网&#xff1a;ESP-IDF 编程指南 - ESP32 VSCode ESP-ID Extension Install 一、前提条件 Visual Studio Code IDE安装ESP-IDF扩展&…

读写锁ReentrantReadWriteLockStampLock详解

如何设计一把读写锁&#xff1f;ReentrantReadWriteLock 读写锁设计思路 读写状态的设计 设计的精髓&#xff1a;用一个变量如何维护多种状态 在 ReentrantLock 中&#xff0c;使用 Sync ( 实际是 AQS )的 int 类型的 state 来表示同步状态&#xff0c;表示锁被一个线程重复获…

ChatGPT AIGC 完成Excel跨多表查找操作vlookup+indirect

VLOOKUP和INDIRECT的组合在Excel中用于跨表查询,其中VLOOKUP函数用于在另一张表中查找数据,INDIRECT函数则用于根据文本字符串引用不同的工作表。具体操作如下: 1.假设在工作表1中,A列有你要查找的值,B列是你希望查询的工作表名称。 2.在工作表1的C列输入以下公式:=VLO…

Unity基础课程之物理引擎6-关于物理材质的使用和理解

每个物体都有着不同的摩擦力。光滑的冰面摩擦力很小&#xff0c;而地毯表面的摩擦力则很大。另外每种材料也有着不同的弹性&#xff0c;橡皮表面的弹性大&#xff0c;硬质地面的弹性小。在Unity中这些现象都符合日常的理念。虽然从原理上讲&#xff0c;物体的摩擦力和弹性有着更…

【交付高质量,用户高增长】-用户增长质量保证方法论 | 京东云技术团队

前言 俗话说&#xff0c;“测试是质量的守护者”&#xff0c;但单凭测试本身却远远不够。大多数情况下&#xff0c;测试像“一面镜子”&#xff0c;照出系统的面貌&#xff0c;给开发者提供修改代码的依据&#xff0c;这个“照镜子”的过程&#xff0c;就是质量评估的过程&…

在 VSCode 中使用 PlantUML

最近&#xff0c;因为工作需要绘制一些逻辑图&#xff0c;我自己现在使用的是 PlantUML 或者 mermaid&#xff0c;相比之下前者更加强大。不过它的环境也麻烦一些&#xff0c;mermaid 在一些软件上已经内置了。但是 PlantUML 一般需要自己本地安装或者使用远程服务器&#xff0…

Paddle GPU版本需要安装CUDA、CUDNN

完整的教程 深度学习环境配置&#xff1a;linuxwindows系统下的显卡驱动、Anaconda、Pytorch&Paddle、cuda&cudnn的安装与说明 - 知乎这篇文档的内容是尽量将深度学习环境配置(使用GPU)所需要的内容做一些说明&#xff0c;由于笔者只在windows和linux下操作过&#xf…

浏览器本地存储之Cookie和webStorage

浏览器本地存储主要包括 Cookie 和 Web Storage 两种机制。它们都是用来在客户端存储数据&#xff0c;以便在浏览器会话之间保持信息或在同一会话中的页面之间共享信息。 一、Cookie 1.1 概念 cookie是客户端与服务器端进行会话使用的一个能够在浏览器本地化存储的技术。简言…

nocos注册中心使用教程

1.下载和安装 进入到官网下载就好了 解压 启动 2.新建提供者模块 2.1新建提供者模块cloudalibaba-provider-payment9001 2.1.1在父项目中新加入依赖 <dependency><groupId>com.alibaba.cloud</groupId><artifactId>spring-cloud-alibaba-depend…

2022 年中职组“ 网络安全 ”赛项-web加固阶段题目

前言 大家好&#xff0c;本章节我将复现一次web加固阶段的操作&#xff0c;给大家看看该怎么操作和截图的具体事项&#xff0c;懂的大佬可以在评论区留言改进&#xff0c;感谢大家的支持&#xff01;接下来就跟随我的步伐一起来操作吧&#xff01; 阶段题目概览 环境搭建 底层…

【Eclipse】Plug-in Development 插件的安装

先按路线找到需要的页面&#xff1a;eclipse–Window–Preferences–Java–Editor–Content Assist 在Work with框中输入&#xff1a;http://download.eclipse.org/releases/2019-06 PS&#xff1a;后面的2019-06是eclipse发行的时间 选择&#xff1a;General Purpose Tools 下…

rhel8 nmcli学习

rhel8我自己用过的配置网路方法有以下几个&#xff1a; &#xff08;1)手动配置ifcfg文件&#xff0c;通过NM来生效。 (2)手动配置ifcfg文件&#xff0c;通过重启NetworkManager.service生效。 (3)通过NM自带工具配置网络&#xff0c;比如nmcli。 (4)使用命令 nutui命令&am…