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

基础算法——前缀和

由于比赛基本都是采用Dev-C++所以,算法篇基本都是采用Dev-C++来解释(版本5.11,c++11)
首先介绍一下前缀和算法

给定一个数组,有q次询问,每次询问:
两个整数l,r,求出数组 l 到 r的结果

遇到问题首先先来分析问题
上图:
在这里插入图片描述
第一种方法,相信大家都会写,所以我们现在来写第二种解法:
在这里插入图片描述
数学中的求和公式,我们可以将其变为:
在这里插入图片描述

那我们为什么要这么做呢?

例如:上面的数组 1 2 3 4 5
用这个公式可以得出 1 3 6 10 15
得出的东西是什么呢?
在这里插入图片描述
可见,每一项就等于自身的值,加上前面的所有项的值
那我们应该如何求区间中的值呢?
数组[r]-数组[l-1]
在这里插入图片描述
要求蓝色的值,我们就要用从数组开始一直到 r 的值减去数组开始一直到 l-1 的值。

证明一下,比如我们要求 l =2,r=5
上面我们已经求得了数组开始一直加到数组结尾,值为15,数组[l-1]的值为1
最终我们所得的值为 14.

下来我们写一下代码:

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1e5+9;
void test()
{int lenth,q;cin>>lenth>>q;ll arr[N],perfix[N];for(int i=1;i<=lenth;i++){cin>>arr[i];}for(int i=1;i<=lenth;i++){perfix[i]=perfix[i-1]+arr[i];}while(q--){int l,r;cin>>l>>r;cout<<perfix[r]-perfix[l-1]<<'\n';}
}
int main()
{int T;cin>>T;while(T--){test();}return 0;
}

在这里插入图片描述
代码没有问题,这里有一点我想提一下,这里的代码,数组arr[0]是不存东西的,是为了方便后面前缀和,有的小伙伴代码风格不同,就是要从0开始,也是可以的
通过调试:
在这里插入图片描述
我们可以看到时这样存储的,我们题目中询问l=2 r=5并不是问下标,而是实打实元素的顺序,要解决这一问题,我们可以
在这里插入图片描述
将perfix[i]=perfix[i-1]+arr[i];改为现在这样这样就妥了

在这里插入图片描述
当然还有别的修改办法,这里就不一 一列举了。

相关文章:

基础算法——前缀和

由于比赛基本都是采用Dev-C所以&#xff0c;算法篇基本都是采用Dev-C来解释&#xff08;版本5.11&#xff0c;c11&#xff09; 首先介绍一下前缀和算法 给定一个数组&#xff0c;有q次询问&#xff0c;每次询问&#xff1a; 两个整数l,r&#xff0c;求出数组 l 到 r的结果 遇…...

spring实例化对象的几种方式(使用XML配置文件)

前言 Spring框架作为一个轻量级的控制反转&#xff08;IoC&#xff09;容器&#xff0c;为开发者提供了多种对象实例化的策略。通过这些策略&#xff0c;开发者可以更加灵活地控制对象的生命周期和依赖关系。无论是通过XML配置、注解配置还是Java配置&#xff0c;Spring都能…...

【二叉树】力扣 129.求根节点到叶子节点数字之和

一、题目 二、思路 每找到一个非空节点&#xff0c;之前路径上的所有节点的数量级都要增加1个单位。例如&#xff0c;当前节点为3&#xff0c;之前的节点路径为1 -> 2&#xff0c;presum 1 * 10 2 12&#xff0c;现在路径变为了 1 -> 2 -> 3&#xff0c;sum pres…...

深度学习物体检测之YOLOV5源码解读

V5比前面版本偏工程化,项目化,更贴合实战 一.V5版本项目配置 (1)整体项目概述 首先github直接查找yolov5&#xff0c;下载下来即可。在训练时&#xff0c;数据是怎么处理的&#xff1f;网络模型架构是怎么设计的(如各层的设计)&#xff1f;yolov5要求是大于python3.8与大于等…...

音频数据采样入门详解 - 给Python初学者的简单解释

音频数据采样入门详解 - 给Python初学者的简单解释 声音是如何变成数字的&#xff1f;什么是采样率&#xff1f;为什么要懂这个&#xff1f;Python小例子总结 大家好&#xff01;今天我们来聊一个有趣的话题&#xff1a;音频数据是如何在计算机中处理的。让我用最简单的方式来解…...

Unity类银河战士恶魔城学习总结(P179 Enemy Archer 弓箭手)

教程源地址&#xff1a;https://www.udemy.com/course/2d-rpg-alexdev/ 本章节实现了敌人弓箭手的制作 Enemy_Archer.cs 核心功能 状态机管理敌人的行为 定义了多个状态对象&#xff08;如 idleState、moveState、attackState 等&#xff09;&#xff0c;通过状态机管理敌人的…...

SpringCloud集成sleuth和zipkin实现微服务链路追踪

文章目录 前言技术积累spring cloud sleuth介绍zipkin介绍Zipkin与Sleuth的协作 SpringCloud多模块搭建Zipkin Server部署docker pull 镜像启动zipkin server SpringCloud 接入 Sleuth 与 Zipkinpom引入依赖 (springboot2.6)appilication.yml配置修改增加测试链路代码 调用微服…...

Python随机抽取Excel数据并在处理后整合为一个文件

本文介绍基于Python语言&#xff0c;针对一个文件夹下大量的Excel表格文件&#xff0c;基于其中每一个文件&#xff0c;随机从其中选取一部分数据&#xff0c;并将全部文件中随机获取的数据合并为一个新的Excel表格文件的方法。 首先&#xff0c;我们来明确一下本文的具体需求。…...

Linux+Docker onlyoffice 启用 HTTPS 端口支持

文章目录 一、需求二、配置2.1 创建容器2.2 进入容器2.3 生成私钥和证书 2.4 测试访问 一、需求 上篇文章介绍了如何搭建一个 onlyoffice 在线预览服务&#xff0c;但是我们实际场景调用该服务的网站是协议是 https 的 &#xff0c;但是 onlyoffice 服务还没做配置&#xff0c…...

在 Visual Studio Code 中编译、调试和执行 Makefile 工程 llama2.c

在 Visual Studio Code 中编译、调试和执行 Makefile 工程 llama2.c 1. Installing the extension (在 Visual Studio Code 中安装插件)1.1. Extensions for Visual Studio Code1.2. C/C1.2.1. Pre-requisites 1.3. Makefile Tools 2. Configuring your project (配置项目)2.1.…...

python中math模块常用函数

文章目录 math模块简介各种三角函数反三角函数取整函数欧几里得距离绝对值最大公约数开根号幂阶乘函数 math模块简介 math模块是python标准库的一部分&#xff0c;提供了对于浮点数相关的数学运算&#xff0c;下面是常用的一些function 各种三角函数反三角函数 math.cos、ma…...

优化 Vue 3 开发体验:配置 Vite 使用 WebStorm 作为 Vue DevTools 的默认编辑器

优化 Vue 3 开发体验&#xff1a;配置 Vite 使用 WebStorm 替代 VS Code 作为 Vue DevTools 的默认编辑器 在 Vue 3 项目开发中&#xff0c;合理配置开发工具可以大大提升我们的工作效率。本文将介绍如何配置 Vite&#xff0c;使其在使用 Vue DevTools 时将默认编辑器从 VS Co…...

【C语言练习(9)—有一个正整数,求是几位数然后逆序打印】

C语言练习&#xff08;9&#xff09; 文章目录 C语言练习&#xff08;9&#xff09;前言题目题目解析结果总结 前言 主要到整数的取余(%)和整数的取商(/)&#xff0c;判断语句if…else if …else的使用 题目 给一个不多于3位的正整数&#xff0c;要求:一、求它是几位数&…...

热敏打印机的控制

首次接触热敏打印机&#xff0c;本来没有特别之处&#xff0c;花了大概十天时间完成一款猫学王热敏打印机&#xff0c;给到客户体验后&#xff0c;客户反馈说打字看起来不明显&#xff0c;打印照片有条纹&#xff0c;所以引起了我对于他的关注&#xff0c;几点不足之处需要优化…...

【closerAI ComfyUI】电商赋能,AI模特套图生产,各种姿势自定义,高度保持人物服饰场景一致性,摆拍街拍专用

closerAIGCcloserAI,一个深入探索前沿人工智能与AIGC领域的资讯平台,我们旨在让AIGC渗入我们的工作与生活中,让我们一起探索AIGC的无限可能性!aigc.douyoubuy.cn 【closerAI ComfyUI】电商赋能,AI模特套图生产,各种姿势自定义,高度保持人物服饰场景一致性,摆拍街拍专用…...

ARM学习(36)静态扫描规则学习以及工具使用

笔者来学习了解一下静态扫描以及其规则,并且亲身是实践一下对arm 架构的代码进行扫描。 1、静态扫描认识 静态扫描:对代码源文件按照一定的规则进行扫描,来发现一些潜在的问题或者风险,因为不涉及代码运行,所以其一般只是发现一些规范或则一些质量问题,当然这些可能存在潜…...

使用 Docker Compose 部署 Redis 主从与 Sentinel 高可用集群

文章目录 使用 Docker Compose 部署 Redis 主从与 Sentinel 高可用集群Redis 主从架构简介Redis Sentinel 简介配置文件1. 主节点配置 (redis-master.conf)2. 从节点配置 (redis-slave1.conf 和 redis-slave2.conf)redis-slave1.confredis-slave2.conf3. Sentinel 配置 (sentin…...

警惕!手动调整服务器时间可能引发的系统灾难

警惕&#xff01;手动调整服务器时间可能引发的系统灾难 1. 鉴权机制1.1 基于时间戳的签名验证1.2 基于会话的认证机制&#xff08;JWT、TOTP&#xff09; 2. 雪花算法生成 ID 的影响2.1 时间戳回拨导致 ID 冲突2.2 ID 顺序被打乱 3. 日志记录与审计3.1 日志顺序错误3.2 审计日…...

MySQL追梦旅途之性能优化

1、索引优化 索引可以显著加速查询操作&#xff0c;但过多或不适当的索引也会带来负面影响&#xff08;如增加写入开销&#xff09;。因此&#xff0c;选择合适的索引至关重要。 创建索引&#xff1a; 为经常用于WHERE子句、JOIN条件和ORDER BY排序的列创建索引。 CREATE I…...

【机器学习】【无监督学习——聚类】从零开始掌握聚类分析:探索数据背后的隐藏模式与应用实例

从零开始掌握聚类分析&#xff1a;探索数据背后的隐藏模式与应用实例 基本概念聚类分类聚类算法的评价指标&#xff08;1&#xff09;内部指标轮廓系数&#xff08;Silhouette Coefficient&#xff09;DB指数&#xff08;Davies-Bouldin Index&#xff09;Dunn指数 &#xff08…...

XML Group端口详解

在XML数据映射过程中&#xff0c;经常需要对数据进行分组聚合操作。例如&#xff0c;当处理包含多个物料明细的XML文件时&#xff0c;可能需要将相同物料号的明细归为一组&#xff0c;或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码&#xff0c;增加了开…...

Golang dig框架与GraphQL的完美结合

将 Go 的 Dig 依赖注入框架与 GraphQL 结合使用&#xff0c;可以显著提升应用程序的可维护性、可测试性以及灵活性。 Dig 是一个强大的依赖注入容器&#xff0c;能够帮助开发者更好地管理复杂的依赖关系&#xff0c;而 GraphQL 则是一种用于 API 的查询语言&#xff0c;能够提…...

vue3 定时器-定义全局方法 vue+ts

1.创建ts文件 路径&#xff1a;src/utils/timer.ts 完整代码&#xff1a; import { onUnmounted } from vuetype TimerCallback (...args: any[]) > voidexport function useGlobalTimer() {const timers: Map<number, NodeJS.Timeout> new Map()// 创建定时器con…...

什么是EULA和DPA

文章目录 EULA&#xff08;End User License Agreement&#xff09;DPA&#xff08;Data Protection Agreement&#xff09;一、定义与背景二、核心内容三、法律效力与责任四、实际应用与意义 EULA&#xff08;End User License Agreement&#xff09; 定义&#xff1a; EULA即…...

python报错No module named ‘tensorflow.keras‘

是由于不同版本的tensorflow下的keras所在的路径不同&#xff0c;结合所安装的tensorflow的目录结构修改from语句即可。 原语句&#xff1a; from tensorflow.keras.layers import Conv1D, MaxPooling1D, LSTM, Dense 修改后&#xff1a; from tensorflow.python.keras.lay…...

《C++ 模板》

目录 函数模板 类模板 非类型模板参数 模板特化 函数模板特化 类模板的特化 模板&#xff0c;就像一个模具&#xff0c;里面可以将不同类型的材料做成一个形状&#xff0c;其分为函数模板和类模板。 函数模板 函数模板可以简化函数重载的代码。格式&#xff1a;templa…...

MySQL 知识小结(一)

一、my.cnf配置详解 我们知道安装MySQL有两种方式来安装咱们的MySQL数据库&#xff0c;分别是二进制安装编译数据库或者使用三方yum来进行安装,第三方yum的安装相对于二进制压缩包的安装更快捷&#xff0c;但是文件存放起来数据比较冗余&#xff0c;用二进制能够更好管理咱们M…...

【p2p、分布式,区块链笔记 MESH】Bluetooth蓝牙通信 BLE Mesh协议的拓扑结构 定向转发机制

目录 节点的功能承载层&#xff08;GATT/Adv&#xff09;局限性&#xff1a; 拓扑关系定向转发机制定向转发意义 CG 节点的功能 节点的功能由节点支持的特性和功能决定。所有节点都能够发送和接收网格消息。节点还可以选择支持一个或多个附加功能&#xff0c;如 Configuration …...

HTML前端开发:JavaScript 获取元素方法详解

作为前端开发者&#xff0c;高效获取 DOM 元素是必备技能。以下是 JS 中核心的获取元素方法&#xff0c;分为两大系列&#xff1a; 一、getElementBy... 系列 传统方法&#xff0c;直接通过 DOM 接口访问&#xff0c;返回动态集合&#xff08;元素变化会实时更新&#xff09;。…...

Linux中《基础IO》详细介绍

目录 理解"文件"狭义理解广义理解文件操作的归类认知系统角度文件类别 回顾C文件接口打开文件写文件读文件稍作修改&#xff0c;实现简单cat命令 输出信息到显示器&#xff0c;你有哪些方法stdin & stdout & stderr打开文件的方式 系统⽂件I/O⼀种传递标志位…...