【代码随想录】区间和——前缀和方法
本博文为《代码随想录》学习笔记,原文链接:代码随想录
题目
原题链接:58. 区间和(第九期模拟笔试)
题目描述
给定一个整数数组 Array,请计算该数组在每个指定区间内元素的总和。
输入描述
第一行输入为整数数组 Array 的长度 n,接下来 n 行,每行一个整数,表示数组的元素。随后的输入为需要计算总和的区间下标:a,b (b > = a),直至文件结束。
输出描述
输出每个指定区间内元素的总和。
输入示例
5
1
2
3
4
5
0 1
1 3
输出示例
3
9
提示信息
数据范围:
0 < n <= 100000
题解
方法一:暴力解法
注意**处代码的写法,之前没有这样写过
#include <bits/stdc++.h>
using namespace std;int main()
{int n,a,b; cin>>n;int nums[n];for(int i=0;i<n;i++){cin>>nums[i];}while(cin>>a>>b)//** 注意这里的写法{int sum=0;for(int i=a;i<=b;i++)sum+=nums[i];cout<<sum<<endl;}return 0;
}
vector初始化
这里纠正之前关于vector的一个误区,vector初始化的方式有以下几种
1、定义空向量
vector<int> a; //相当于空数组
2、定义具有10个整型元素的向量
vector<int> a(10); //相当于a[10]
3、定义具有10个整型元素的向量,且赋予每个元素初值为1
vector<int> a(10,1); //相当于a[10] = {1}
4、定义与向量b具有相同值的向量a
vector<int> a(b); //将向量b赋值给向量a,即向量a等于向量b
5、将向量b中下标0-2(共三个)的元素赋值给a
//第一个数据是起始地址,第二个数据是结束地址(不包括),第二个数据就是你要截取的长度加1
vector<int> a(b.begin(), b.begin()+3);6、从数组中获得初值
int b[7] = {1,2,3,4,5,6,7}; //定义整形数组
vector<int> a(b, b+7); //将数组b赋值给a,第一个数据是起始地址,第二个数据是结束地址(不包括)
7、二维数组初始化
vector<vector<int>> a; //初始化为int型二维数组,相当于int a[][]
下标只能获取已存在的元素,所以以下赋值方法对第一种初始化方法是错误的
for(int i=0; i<10; i++){a[i] = i; //应使用a.push_back(i)
}
但当数组中已经存在元素则可以使用上述方法进行赋值,因此方法一还可以写成如下形式:
#include <iostream>
#include <vector>
using namespace std;
int main() {int n, a, b;cin >> n;vector<int> vec(n);for (int i = 0; i < n; i++) cin >> vec[i];while (cin >> a >> b) {int sum = 0;// 累加区间 a 到 b 的和for (int i = a; i <= b; i++) sum += vec[i];cout << sum << endl;}
}
提交代码,发现超时了

当查询范围和查询次数较大时,这种暴力解法的时间复杂度时非常大的。
方法二:前缀和方法
对前缀和的思路进行举例说明,例如我们要统计vec[i]这个数组上的区间和。
我们先做累加,即p[i]表示下标0到i的vec[i]累加之和。如图:

如果,我们想统计,在vec数组上 下标 2 到下标 5 之间的累加和,那就用 p[5] - p[1] 就可以了。
p[1] = vec[0] + vec[1];
p[5] = vec[0] + vec[1] + vec[2] + vec[3] + vec[4] + vec[5];
p[5] - p[1] = vec[2] + vec[3] + vec[4] + vec[5];

p[5] - p[1] 就是 红色部分的区间和。
而 p 数组是我们之前就计算好的累加和,所以后面每次求区间和的之后 我们只需要 O(1) 的操作。
特别注意: 在使用前缀和求解的时候,要特别注意 求解区间。
如上图,如果我们要求 区间下标 [2, 5] 的区间和,那么应该是 p[5] - p[1],而不是 p[5] - p[2]。在解题时可以通过画图来帮助理解。
编写代码如下:
#include <bits/stdc++.h>
using namespace std;int main()
{int n,a,b; cin>>n;int nums[n];int p[n];//前缀和数组 for(int i=0;i<n;i++){cin>>nums[i];p[i]=p[i-1]+nums[i];}while(cin>>a>>b){int sum=p[b]-p[a-1];cout<<sum<<endl;}return 0;
}

《代码随想录》中给出的代码如下:
#include <iostream>
#include <vector>
using namespace std;
int main() {int n, a, b;cin >> n;vector<int> vec(n);vector<int> p(n);int presum = 0;for (int i = 0; i < n; i++) {cin >> vec[i];presum += vec[i];p[i] = presum;}while (cin >> a >> b) {int sum;if (a == 0) sum = p[b];else sum = p[b] - p[a - 1];cout << sum << endl;}
}
C++ 代码 面对大量数据 读取 输出操作,最好用scanf 和 printf,耗时会小很多:
#include <iostream>
#include <vector>
using namespace std;
int main() {int n, a, b;cin >> 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);}
}
相关文章:
【代码随想录】区间和——前缀和方法
本博文为《代码随想录》学习笔记,原文链接:代码随想录 题目 原题链接:58. 区间和(第九期模拟笔试) 题目描述 给定一个整数数组 Array,请计算该数组在每个指定区间内元素的总和。 输入描述 第一行输入为…...
Bug 解决 | 前端项目无法正确安装依赖?
目录 1、网络问题 2、权限问题 3、版本冲突 4、缓存问题 5、依赖配置错误 6、系统环境问题 前端项目和后端项目一样,都需要用到很多第三方的类库依赖。目前基本上我们主流的前端项目都使用 Npm、Yarn 等包管理工具来管理项目依赖,正常情况下通过执…...
【mysql 第四篇章】bin log 的作用是啥呢?
一、redo Log 介绍 redo log 是一种偏向物理性质的重做日志,因为他里面记录类似的这样的东西,“对那个数据也中的什么记录,做了个什么修改”。它是 InnoDB 存储引擎特有的东西。 二、bin Log 日志 bin log 叫做归档日志,它里面…...
Linux 操作系统:基于环形队列的生产者消费者模型
Linux 操作系统:基于环形队列的生产者消费者模型 一、前言二、大致框架二、P操作、V操作三、生产者生产数据四、生产者获取数据五、代码测试六、所有代码 一、前言 环形队列采用数组模拟,用模运算来模拟环状特性。和基于阻塞队列的生产者消费者模型不同的…...
python求解二次方程
为了找到x和y之间的关系,并假设这种关系是一个二次函数,我们可以使用numpy的polyfit函数来拟合一个二次方程(即形式为y ax^2 bx c的方程)。然后,我们可以使用matplotlib来绘制散点图,并在图上添加最佳拟…...
Spring框架面试总结
Spring基础 什么是spring框架 Spring 框架是一个用于构建企业级 Java 应用程序的开源框架。【Java项目快速构建轻量级框架】我们一般说 Spring 框架指的都是 Spring Framework,它是很多模块的集合,使用这些模块可以很方便地协助我们进行开发。【根据模…...
java之网络编程篇
前言 网络编程就是计算机和计算机之间通过网络进行数据传输,下面介绍一些概念和如何实现UDP和TCP两种模式的传输。 一、常见的软件架构C/S和B/S C/S架构需要一个客户端软件程序服务器 B/S只需要打开网页服务器 C/S架构的优缺点和应用场景 优点:画面可以…...
stm32f103c8t6与TB6612FNG解耦测试
stm32f103c8t6与TB6612FNG解耦测试 本文操作方式: 忽略底层,只做上层, 所以前面全部照搬步骤,重在调试 文章目录 stm32f103c8t6与TB6612FNG解耦测试本文操作方式:创建基本工程(1)跳转此链接,创建(2)创建电机驱动文件夹(3)PWM原理(4)电机转动控制 oled调试和key调试(5)OLED转速…...
2253336 - 资源库 - OAC0 中的脱机状态
症状 资源库的状态显示为离线。 环境 SAP 内容服务器 6.50 或更高版本与 MaxDB 存储媒介结合使用对于状态为离线的资源库,测试报表 RSCMST 运行正常资源库可在应用程序中使用,没有任何问题 重现问题 启动事务 OAC0双击资源库按 "CSADMIN"…...
uni-app总结
1. <u-form-item label"报废人" ><u--input v-model"model.remark" border"bottom" placeholder"请输入"></u--input> </u-form-item> border"bottom" 报废日期 为了...
【JavaEE初阶】线程安全的集合类
📕 引言 我们之前讲过的集合类,,大部分都不是线程安全的. Vector, Stack, HashTable, 是线程安全的(都是自带了synchronized,不建议用), 其他的集合类不是线程安全的。 注意:加锁不能保证线程一定安全,不加锁也不能确定线程一定…...
关于Vue项目npm快捷键,点击run启动报错,及npm i也报错的解决办法
1.配置idea的npm 2.点击运行按钮 3.结果 分析原因及问题: npm i npm run dev 由于是刚刚从gitlab新拉的前端代码,可能没有用命令install过类似于没有编译过,所以执行一下上面的命令 结果报错如下: F:\tbyf\qjyy\hip-manager-ui&…...
React中,className属性自定义组件不生效的问题
在React中,className属性不仅适用于原生的HTML元素,也可以用于自定义组件。实际上,className属性是React中通用的属性,可以应用于任何React元素,无论是原生的HTML元素还是自定义的组件。 为什么使用className而不是cl…...
Ubuntu22.04搭建fabric开发环境、开发环境下运行链码
在智能合约开发过程中,开发人员需要一种快速、迭代地测试链码包的方法,而无需为每次修改运行链码生命周期命令。 使用 Fabric 二进制文件并启动peer处于开发模式(“DevMode”),然后将链码连接到peer。它允许您启动链代…...
[BSidesCF 2019]Kookie1
打开题目,看到 根据提示,账号:cookie。密码:monster。试一下登录,登陆成功 抓包看看信息 根据提示, 看一下返回包 账号要加username要改成admin,改一下试试 构造cookie 直接得到flag flag{c…...
LCM红外小目标检测
根据站内的matlab代码修改成python版本。 import numpy as np import matplotlib.pyplot as plt import cv2 from pylab import mpl# 设置中文显示字体 mpl.rcParams["font.sans-serif"] ["SimHei"]def LCM_computation(patch_LCM_in):row, col patch_L…...
振德医疗选择泛微千里聆RPA,助力电商、人事业务流程自动化
振德医疗用品股份有限公司成立于1994年,中国A股上市公司,是医用敷料和感控防护产品主要的供应商之一。 (图片素材来自振德医疗官网) 振德医疗的业务在线上线下齐发力。目前拥有5个国内生产基地,3个海外工厂࿰…...
VBA高级应用30例应用3在Excel中的ListObject对象:创建表
《VBA高级应用30例》(版权10178985),是我推出的第十套教程,教程是专门针对高级学员在学习VBA过程中提高路途上的案例展开,这套教程案例与理论结合,紧贴“实战”,并做“战术总结”,以…...
IP 地址在 SQL 注入攻击中的作用及防范策略
数据库在各个领域的逐步应用,其安全性也备受关注。SQL 注入攻击作为一种常见的数据库攻击手段,给网络安全带来了巨大威胁。今天我们来聊一聊SQL 注入攻击的基本知识。 SQL 注入攻击的基本原理 SQL 注入是通过将恶意的 SQL 代码插入到输入参数中…...
Unity VR黑屏
picosdk里面的,有修改 using System.Collections; using System.Collections.Generic; using UnityEngine;public class ScreenFade : MonoBehaviour {[Tooltip("颜色")]public Color fadeColor new Color(0.0f, 0.0f, 0.0f, 1.0f);private int renderQ…...
Day131 | 灵神 | 回溯算法 | 子集型 子集
Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣(LeetCode) 思路: 笔者写过很多次这道题了,不想写题解了,大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...
IGP(Interior Gateway Protocol,内部网关协议)
IGP(Interior Gateway Protocol,内部网关协议) 是一种用于在一个自治系统(AS)内部传递路由信息的路由协议,主要用于在一个组织或机构的内部网络中决定数据包的最佳路径。与用于自治系统之间通信的 EGP&…...
【机器视觉】单目测距——运动结构恢复
ps:图是随便找的,为了凑个封面 前言 在前面对光流法进行进一步改进,希望将2D光流推广至3D场景流时,发现2D转3D过程中存在尺度歧义问题,需要补全摄像头拍摄图像中缺失的深度信息,否则解空间不收敛…...
springboot整合VUE之在线教育管理系统简介
可以学习到的技能 学会常用技术栈的使用 独立开发项目 学会前端的开发流程 学会后端的开发流程 学会数据库的设计 学会前后端接口调用方式 学会多模块之间的关联 学会数据的处理 适用人群 在校学生,小白用户,想学习知识的 有点基础,想要通过项…...
C#中的CLR属性、依赖属性与附加属性
CLR属性的主要特征 封装性: 隐藏字段的实现细节 提供对字段的受控访问 访问控制: 可单独设置get/set访问器的可见性 可创建只读或只写属性 计算属性: 可以在getter中执行计算逻辑 不需要直接对应一个字段 验证逻辑: 可以…...
iview框架主题色的应用
1.下载 less要使用3.0.0以下的版本 npm install less2.7.3 npm install less-loader4.0.52./src/config/theme.js文件 module.exports {yellow: {theme-color: #FDCE04},blue: {theme-color: #547CE7} }在sass中使用theme配置的颜色主题,无需引入,直接可…...
[大语言模型]在个人电脑上部署ollama 并进行管理,最后配置AI程序开发助手.
ollama官网: 下载 https://ollama.com/ 安装 查看可以使用的模型 https://ollama.com/search 例如 https://ollama.com/library/deepseek-r1/tags # deepseek-r1:7bollama pull deepseek-r1:7b改token数量为409622 16384 ollama命令说明 ollama serve #:…...
计算机系统结构复习-名词解释2
1.定向:在某条指令产生计算结果之前,其他指令并不真正立即需要该计算结果,如果能够将该计算结果从其产生的地方直接送到其他指令中需要它的地方,那么就可以避免停顿。 2.多级存储层次:由若干个采用不同实现技术的存储…...
Copilot for Xcode (iOS的 AI辅助编程)
Copilot for Xcode 简介Copilot下载与安装 体验环境要求下载最新的安装包安装登录系统权限设置 AI辅助编程生成注释代码补全简单需求代码生成辅助编程行间代码生成注释联想 代码生成 总结 简介 尝试使用了Copilot,它能根据上下文补全代码,快速生成常用…...
C# WPF 左右布局实现学习笔记(1)
开发流程视频: https://www.youtube.com/watch?vCkHyDYeImjY&ab_channelC%23DesignPro Git源码: GitHub - CSharpDesignPro/Page-Navigation-using-MVVM: WPF - Page Navigation using MVVM 1. 新建工程 新建WPF应用(.NET Framework) 2.…...

