前缀和处理数组区间之和问题

1.什么是区间和问题

“区间和问题”通常指的是涉及计算或处理数组或数列某个子区间(即一段连续元素)的总和的类型问题。这类问题可能有多种变体和不同的复杂度,但基本思想都是在给定的区间内快速计算总和或处理与区间和相关的操作。

2.例题

题目描述

给定一个整数数组 Array,请计算该数组在每个指定区间内元素的总和。

输入描述

第一行输入为整数数组 Array 的长度 n,接下来 n 行,每行一个整数,表示数组的元素。随后的输入为需要计算总和的区间下标:a,b (b > = a),直至文件结束。

输出描述

输出每个指定区间内元素的总和。

3.解题思路

在看到题目的第一反应,大多数同学认为这是一道非常简单的数组求和问题,只需要将区间中对应下标的元素依次相加即可,但通过这种方法提交问题往往会编译超时。why?取极端情况:如果我次次查询的范围都是n-1到0,那么算法的复杂度是O(n * m) m,也就是查询的次数。可见查询次数非常多,而且时间也很长。
所以,为了加速区间和的查询,可以创建一个前缀和数组。前缀和数组 P[i] 表示原数组 A 从第1个元素到第 i 个元素的和。利用前缀和数组可以在 O(1) 时间内计算任意区间的和:
在这里插入图片描述

通过上面的图示可以看出,Sum(a,b)=P[b]−P[a−1]
注意这里a不可以为0,a为0要单独考虑:Sum(0,b)=P[b]
计算前缀和数组的时间复杂度是 O(n),每个查询时间复杂度是 O(1)。
在这里插入图片描述

有了前缀和数组之后,我们就可以在输入原数组元素时,设定一个累加变量,输入一次累加变量就增加一次。而前缀和数组的每个元素大小就是对应的累加变量的大小。
代码如下:

# include <iostream>
# include <vector>
using namespace std;
int main(){int n,a,b;scanf("%d",&n);vector<int> vec(n);vector<int> p(n);int presum=0;for(int i=0;i < n;i++){scanf("%d",&vec[i]);presum+=vec[i];p[i]=presum;}while(~scanf("%d%d", &a, &b)){int sum;if(a==0) sum=p[b];else sum = p[b]-p[a-1];printf("%d\n",sum);}
}

4.小节

1.scanf 函数返回成功读取的输入项的数量(如成功读取两个整数则返回 2),如果遇到输入错误或到达文件末尾,scanf 会返回 EOF(通常为 -1)。while (~scanf("%d%d", &a, &b)) 这行代码的意思是对 scanf 的返回值进行按位取反,然后将结果用于 while 循环的条件判断。
2.当对 scanf 的返回值使用 ~ 时,如果 scanf 成功读取了输入项,返回值将不为 0,而取反后的结果通常为一个负数;如果 scanf 返回 -1(即 EOF),则 ~(-1) 将得到 0,这时循环会停止。
3.C++ 代码中面对大量数据的读取、输出操作时,最好用scanf 和 printf,而不是cin和cout。因为scanf和printf耗时会小很多
4.区间和问题是许多编程竞赛和算法面试中常见的题型,掌握这些问题的高效解法对提升算法和数据结构的能力非常重要。

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

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

相关文章

常见的框架漏洞

ThinkPHP 首先我们打开一个环境 然后进行远程命令执行代码 然后进行远程代码执行 ?sindex/think\app/invokefunction&functioncall_user_func_array&vars[0]phpinfo&vars[1][]-1 在网页中输出phpinfo getshell ?sindex/think\app/invokefunction&function…

c语言基础知识

ASCII码 字符A~Z的ASCII码值从65~90 • 字符a~z的ASCII码值从97~122 • 对应的⼤⼩写字符(a和A)的ASCII码值的差值是32 • 数字字符0~9的ASCII码值从48~57 • 换⾏ \n 的ASCII值是&#xff1a;10 • 在这些字符中ASCII码值从0~31这32个字符是不可打印字符&#xff0c;⽆法打印在…

sql实战cmseasy

环境搭建 这里我们用phpstady搭建 版本是cmseasy5.5 未授权访问 这里ip的方法获取客户端的ip 这里的意思是当你的server ip等于 客户端ip并且get传参 get(ishtml)1的情况下他会直接return 他就不会检查后面是不是admin&#xff0c;而他这个IP是从X_FORWARDED_FOR获取&…

Spring Boot 3.x Rest API统一异常处理最佳实践

上一篇&#xff1a;Spring Boot 3.x Rest API最佳实践之统一响应结构 在Spring MVC应用中&#xff0c;要对web表示层所抛出的异常进行捕获处理有多种方式&#xff0c;具体的可参考著名国外Spring技术实战网站baeldung上的相关话题。Spring Boot对Spring MVC应用中抛出的异常以…

RNN循环网络层

文章目录 1、简介2、RNN 网络原理3、PyTorch RNN 层的使用3.1、RNN送入单个数据3.2、RNN层送入批量数据 4、RNN三个维度4.1、解释4.2、输入数据的组织4.3、示例4.4、为什么需要这种格式&#xff1f;4.5、小结 &#x1f343;作者介绍&#xff1a;双非本科大三网络工程专业在读&a…

苹果手机数据被抹除还能恢复吗?这两个方法强烈推荐

苹果手机数据被抹除还能恢复吗&#xff1f;我们在使用苹果手机时&#xff0c;有时由于误操作、系统故障或升级失败等原因&#xff0c;导致手机照片、备忘录、视频、联系人等数据被意外抹除。 面对这类情况&#xff0c;我们应该怎么办&#xff1f;下面牛小编给大家的分享2个方法…

记录使用FlinkSql进行实时工作流开发

使用FlinkSql进行实时工作流开发 引言Flink SQL实战常用的Connector1. MySQL-CDC 连接器配置2. Kafka 连接器配置3. JDBC 连接器配置4. RabbitMQ 连接器配置5. REST Lookup 连接器配置6. HDFS 连接器配置 FlinkSql数据类型1. 基本数据类型2. 字符串数据类型3. 日期和时间数据类…

论文解读,神经网络全梯度表示《Full-Gradient Representation for Neural Network Visualization》

导语 这篇论文介绍了一种新的工具&#xff0c;称为全梯度&#xff0c;用于解释神经网络的响应。这个全梯度的概念将神经网络的响应分解为两个部分&#xff1a;输入灵敏度和每个神经元的灵敏度分量。 输入灵敏度&#xff1a;输入灵敏度指的是对于神经网络输出的影响程度。它反…

Python试讲

Python试讲 导语Python简介Python及其特点如何使用Python Python与计算计算变量 导语 本次试讲内容如下&#xff1a;Python简介与使用&#xff0c;Python与基本运算 辅助教材为 《趣学Python编程》和《Python编程从入门到实践》 Python简介 Python是目前入门最简单最好学的…

NSSCTF练习记录:[SWPUCTF 2021 新生赛]jicao

题目&#xff1a; 这段PHP代码的意思是&#xff1a; 对index.php文件进行语法高亮显示&#xff0c;插入flag.php文件&#xff0c;变量id的值为POST传递的值&#xff0c;变量json的值为GET传递的json类型的值。当id值为wllmNB且json中含有键为“x”&#xff0c;值为“wllm”的时…

数据结构:栈与队列OJ题

目录 前言 一、用栈实现队列 二、用队列实现栈 三、括号匹配问题 前言 前面讲了栈和队列的基础知识&#xff0c;今天来巩固一下加深理解&#xff0c;这里说明一下&#xff0c;因为现在都是在用C语言写&#xff0c;这些OJ题里都要用到前面实现栈和队列的代码&#xff0c;每道题…

告别数据丢失烦恼,转转数据恢复和另外三款工具助你一臂之力!

不知道大伙儿有没有和我一样&#xff0c;到哪都喜欢拍照片和视频&#xff0c;加上办公上也是七七八八的各种格式的文件实在是多&#xff0c;所以电脑和手机等等设备上经常内存爆满需要清理&#xff0c;难免会出现不小心误删或者格式化、清空等等的情况&#xff0c;用过几款和转…

Journyx项目管理软件 soap_cgi.pyc XXE漏洞复现

0x01 产品简介 Journyx-Journyx成立于1996年,提供自托管项目管理解决方案ProjectXecute。主要功能包括资源跟踪、待办事项列表、任务分配以及与MS Project的集成。要运行ProjectXecute,需要Windows 2003或更高版本、IIS Web服务器和Intel处理器。也可以在Linux、Solaris、AI…

#子传父父传子props和emits #封装的table #vue3

#子传父&父传子props和emits #封装的table #vue3 父组件&#xff1a;emits defineEmits props 子组件&#xff1a; 子组件 <template><el-table v-bind"$attrs" ref"innerTableRef" v-loading"loading" border :data"tabl…

力扣刷题-轮转数组

&#x1f308;个人主页&#xff1a;羽晨同学 &#x1f4ab;个人格言:“成为自己未来的主人~” 首先&#xff0c;我们现在这里提供的是一种特别简单的思路&#xff0c;我们先来看一下这段代码&#xff1a; void rotate(int* nums, int numsSize, int k) {k%numsSize;int n…

git clone private repo

Create personal access token Clone repo $ git clone https://<user_name>:<personal_access_tokens>github.com/<user_name>/<repo_name>.git

5个适用于Linux系统的PDF转Word工具

凭借其跨平台和设备的统一标准、兼容性和规模小巧等主要优点&#xff0c;可携带文档格式&#xff08;PDF&#xff09;可谓最主流的文件格式之一。 市面上有许多查看PDF文件的强大工具&#xff0c;因此所有Linux系统的用户都可以根据自身喜好找到合适的PDF查看工具。然而&#x…

Linux从0到1——基础IO(上)【文件描述符/重定向/缓冲区】

Linux从0到1——基础IO&#xff08;上&#xff09; 1. 预备知识2. 复习一下常见的C语言文件接口3. 系统调用接口3.1 函数传参小技巧——标志位3.2 使用系统调用接口3.2.1 open3.2.2 write3.2.3 read 4. 文件描述符fd4.1 fd的本质4.2 理解struct file结构体4.3 fd的分配规则 5. …

BES(恒玄)平台log分析

前言 恒玄软件调试和分析基本是通过日志形式分析的&#xff0c;今天就详细说下日志组成和常用分析方法 1.日志组成解析 bes日志组成一般说由以下组成&#xff1a;tick时钟 模块log打印所在线程编码log内容 [17:31:22.834] 21786/NONE / 2 | CPU USAGE: busy18 light8…

WebStorm格式化JSON,将一行很长的JSON展开

webstorm json格式化插件将一行很长的json展开 在WebStorm中&#xff0c;要展开很长的JSON行&#xff0c;可以使用内置的JSON格式化功能。 打开WebStorm&#xff0c;并打开包含JSON的文件。 选择JSON文件中的任意部分。 按下快捷键 CtrlAltL (Windows/Linux) 或 CmdAltL (Ma…