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

【前缀和与差分 C/C++】洛谷 P8218 求区间和

news 来源：原创 2025/8/24 4:02:54

2025 - 03 - 09 - 第 72 篇
Author: 郑龙浩 / 仟濹
【前缀和与差分 C/C++】

文章目录

洛谷 P8218 求区间和
- 题目描述
- 输入格式
- 输出格式
- 输入输出样例 #1
- - 输入 #1
  - 输出 #1
- 说明/提示
- 思路
- 代码

洛谷 P8218 求区间和

题目描述

给定 $n$ 个正整数组成的数列 $a_1, a_2, \cdots, a_n$ 和 $m$ 个区间 $l_i,r_i]$ ，分别求这 $m$ 个区间的区间和。

对于所有测试数据， $n,m\le10^5,a_i\le 10^4$

输入格式

第一行，为一个正整数 $n$ 。

第二行，为 $n$ 个正整数 $a_1,a_2, \cdots ,a_n$

第三行，为一个正整数 $m$ 。

接下来 $m$ 行，每行为两个正整数 $l_i,r_i$ ，满足 $1\le l_i\le r_i\le n$

输出格式

共 $m$ 行。

第 $i$ 行为第 $i$ 组答案的询问。

输入输出样例 #1

输入 #1

输出 #1

10
5

说明/提示

样例解释：第 $1$ 到第 $4$ 个数加起来和为 $10$ 。第 $2$ 个数到第 $3$ 个数加起来和为 $5$ 。

对于 $\%$ 的数据： $n,m\le 1000$ ；

对于 $\%$ 的数据： $\le n, m\le 10^5$ ， $\le a_i\le 10^4$

思路

典型的的一维前缀和做法，不做具体的描述了。

我已将常规的一维前缀和笔记详细记录，具体内容可见我的博客，如下

一维前缀和算法
https://blog.csdn.net/m0_60605989/article/details/146117026?fromshare=blogdetail&sharetype=blogdetail&sharerId=146117026&sharerefer=PC&sharesource=m0_60605989&sharefrom=from_link

代码

// 洛谷P8218求区间和
// Author: 郑龙浩 / 仟濹
// Time: 2025-03-09
// 这道题是一个明显的一维前缀和
#include <bits/stdc++.h>
using namespace std;
// 列表
vector <int> arr;
// 前缀和数组
vector <int> sum;
int num, m;
// 计算区间和的函数 - 利用前缀和
int get_sum(int left, int right){int ans;// 注意判断，如果left是0,0-1 == -1,没有这个下标，不合法，应该特判if (left == 0)  return sum[right];// 正常套用公式即可ans = sum[right] - sum[left - 1];return ans;
}
int main( void ){cin >> num;arr.resize(num); // 设置 arr 原数列大小sum.resize(num); // 设置 sum 前缀和 大小// 输入数列for (int i = 0; i < num; i ++)cin >> arr[i];cin >> m;// 计算前缀和sum[0] = arr[0];for(int i = 1; i < num; i ++){sum[i] = sum[i - 1] + arr[i];}int left, right;// 输入 m 个区间，边输入边运算for (int i = 0; i < m; i ++){cin >> left >> right; // 输入的是第几个，而不是下标left -= 1; // 变为下标right -= 1; // 变为下标cout << get_sum(left, right) << endl;}return 0;
}

【前缀和与差分 C/C++】洛谷 P8218 求区间和

2025 - 03 - 09 - 第 72 篇 Author: 郑龙浩 / 仟濹【前缀和与差分 C/C】文章目录洛谷 P8218 求区间和题目描述输入格式输出格式输入输出样例 #1输入 #1输出 #1 说明/提示思路代码洛谷 P8218 求区间和题目描述给定 n n n 个正整数组成的数列 a 1 , a 2 , ⋯ , a n a_…...

编程日记 2025/8/24 4:02:54

数据库二三事（14）

备份与恢复数据库备份具体内容包括数据库结构，对象与数据，造成数据丢失的原因有： 存储介质故障（硬件损耗） 用户操作错误（人工） 服务器故障（软硬都可能） 病毒侵害 …...

编程日记 2025/8/24 3:59:05

C++之list

list是链表的意思，由一个个节点组成一、基本接口使用： （1）与vector相同，有个尾插，也可以使用迭代器遍历： void test_list1() {list<int> lt;lt.push_back(1);lt.push_back(2);lt.push…...

编程日记 2025/8/23 4:11:11

数据增强术：如何利用大模型（LLMs）来模拟不同的扰动类型以增强信息提取任务的鲁棒性

一、对抗样本库构建 1. 基于LLMs的领域针对性扰动设计对抗样本生成替换实体、三元组和触发器（Replace Entity, Triple, and Trigger）使用LLMs（如GPT-4）来替换句子中的实体、关系三元组或事件触发器，同时保持其类型不变，并确保其他内容不受影响： xxx名称（如“x方” →…...

编程日记 2025/8/24 4:02:34

《Gradio : AI awesome-demos》 This is a list of some wonderful demos & applications built with Gradio. Heres how to contribute yours! 🖊️ Natural language processing Demo name (link to demo)input type(s)output type(s)status badgeruDALL-ET…...

编程日记 2025/8/24 4:02:31

物联网中如何增加其可扩展性协议网络设备还包括软件层面上的

物联网（IoT）系统的可扩展性是指系统能够随着设备数量、数据流量和业务需求的增长而灵活扩展的能力。为了增加物联网的可扩展性，需要从协议、网络、设备和软件等多个层面进行优化和设计。以下是一些具体的策略和方法： 1. 协议层面的可扩展性 1.1 采用轻量级协议轻量级协议…...

编程日记 2025/8/24 4:00:40

【每日学点HarmonyOS Next知识】对话框去掉圆角、数组拼接、自定义对话框依附某个控件、平移动画、页面栈管理

1、 HarmonyOS CustomDialog怎么去掉左右和底部的透明以及圆角？ CustomDialog怎么去掉左右和底部的透明以及圆角设置customStyle为true即可开启使用自定义样式。设置borderRadius为0去掉圆角属性。属性用法参考文档：https://developer.huawei.com/c…...

编程日记 2025/8/24 4:02:32

Unity 通用UI界面逻辑总结

概述在游戏开发中，常常会遇到一些通用的界面逻辑，它不论在什么类型的游戏中都会出现。为了避免重复造轮子，本文总结并提供了一些常用UI界面的实现逻辑。希望可以帮助大家快速开发通用界面模块，也可以在次基础上进行扩展修改&…...

编程日记 2025/8/24 4:01:08

【网络】HTTP协议、HTTPS协议

HTTP与HTTPS HTTP协议概述 HTTP（超文本传输协议）：工作在OSI顶层应用层，用于客户端（浏览器）与服务器之间的通信,B/S模式无状态：每次请求独立，服务器不保存客户端状态（通过Cookie/Session扩展状态管理）。基于TCP：默认端口80（HTTP）、443（HTTPS），保证可靠传输。请…...

编程日记 2025/8/18 8:04:12

计算机网络——交换机

一、什么是交换机？ 交换机（Switch）是局域网（LAN）中的核心设备，负责在数据链路层（OSI第二层）高效转发数据帧。它像一位“智能交通警察”，根据设备的 MAC地址精准引导数…...

编程日记 2025/8/16 10:07:14

机器学习：愚者未完成的诗篇（零）

当算法在数据海洋中打捞支离破碎的韵律时，机器学习系统展现出的智慧如同断臂的维纳斯雕像——完美与残缺构成令人战栗的美学悖论。愚者，在词语的混沌中编织逻辑经纬，却总在即将触及诗性本质的瞬间，暴露出认知维度的致命裂隙。一…...

编程日记 2025/8/24 4:00:16

解锁DeepSpeek-R1大模型微调：从训练到部署，打造定制化AI会话系统

目录 1. 前言 2.大模型微调概念简述 2.1. 按学习范式分类 2.2. 按参数更新范围分类 2.3. 大模型微调框架简介 3. DeepSpeek R1大模型微调实战 3.1.LLaMA-Factory基础环境安装 3.1大模型下载 3.2. 大模型训练 3.3. 大模型部署 3.4. 微调大模型融合基于SpirngBootVue2…...

编程日记 2025/8/24 4:02:53

性能测试和Jmeter

文章目录前言性能测试理论知识什么是性能？什么是性能测试？性能测试的作用性能测试与功能测试的区别性能测试常见术语性能测试的策略基准测试负载测试稳定性测试压力测试并发测试常见性能测试指标响应时间并发数吞吐量点击数和错误率资源使用率性能测试…...

编程日记 2025/8/19 22:34:59

Linux网络之数据链路层协议

目录数据链路层 MAC地址与IP地址数据帧 ARP协议 NAT技术代理服务器正向代理反向代理上期我们学习了网络层中的相关协议，为IP协议。IP协议通过报头中的目的IP地址告知了数据最终要传送的目的主机的IP地址，从而指引了数据在网络中的一步…...

编程日记 2025/8/24 4:01:10

数据结构第八节：红黑树（初阶）

【本节要点】红黑树概念红黑树性质红黑树结点定义红黑树结构红黑树插入操作的分析一、红黑树的概念与性质 1.1 红黑树的概念红黑树 ，是一种二叉搜索树 ，但在每个结点上增加一个存储位表示结点的颜色，可以是 Red和 Black 。通过对任何…...

编程日记 2025/8/24 3:59:03

【大模型知识点】位置编码——绝对位置编码，相对位置编码，旋转位置编码RoPE

由于Transformer 中的自注意模块具有置换不变性（不关心输入序列的顺序），因此需要使用位置编码来注入位置信息以建模序列，使模型能够区分不同位置的 token，并捕捉序列的顺序关系。在介绍一些位置编码方法前&#xff0…...

编程日记 2025/8/17 17:48:19

【大模型篇】推理模型大作战（QwQ-32B vs DeepSeek-R1）

大家好，我是大 F，深耕AI算法十余年，互联网大厂技术岗。分享AI算法干货、技术心得。欢迎关注《大模型理论和实战》、《DeepSeek技术解析和实战》，一起探索技术的无限可能！写在前面当我让QwQ-32B vs DeepSeek-R1 写一封未来自己的信大家更喜欢哪种风格？ QwQ-32B 模…...

编程日记 2025/8/16 10:06:19

【汇编语言】单片机程序执行过程

一、任务需求指示灯LED4闪烁，亮0.5秒，灭0.5秒，无限循环二、针对硬件的编程 1、确定原理图2、确定硬件的物理关系三、设计步骤 1.用自己的语言描述工作流程 1.1指示灯LED4亮1.2延时0.5秒1.3指示灯LED4灭1.4延时0.5秒1.5跳转到1.1步 …...

编程日记 2025/8/24 4:01:07

MYSQL之创建数据库和表

创建数据库db_ck （下面的创建是最好的创建方法，如果数据库存在也不会报错，并且指定使用utf8mb4） show databases命令可以查看所有的数据库名，可以找到刚刚创建的db_ck数据库使用该数据库时，发现里面没有…...

编程日记 2025/8/24 4:00:14

MybatisPlus

1.增删改查入门案例： 首先导入依赖： <dependency><groupId>com.baomidou</groupId><artifactId>mybatis-plus-boot-starter</artifactId><version>3.5.3.1</version></dependency> 然后这些增删改查…...

编程日记 2025/8/24 4:02:32

HCIE云计算学什么？怎么学？未来职业发展如何？

随着云计算成为IT行业发展的主流方向，HCIE云计算（华为认证云计算专家）作为华为认证体系中的高端认证之一，逐渐成为了许多网络工程师和IT从业者提升职业竞争力的重要途径。那么，HCIE云计算究竟学什么内容，如…...

编程日记 2025/8/24 4:01:09

小程序 -- uni-app开发微信小程序环境搭建（HBuilder X+微信开发者工具）

目录前言一软件部分 1. 微信开发者工具 2. HBuilder X 开发工具二配置部分 1. 关于 HBuilder X 配置 2. 关于微信开发工具配置三运行项目 1. 新建项目 2. 代码编写 3. 内置浏览器编译 4. 配置小程序 AppID获取注意四实现效果前言 uni-app开发小程…...

编程日记 2025/8/24 4:02:32

多线程-线程本地变量ThreadLocal

简介 ThreadLocal是线程本地变量，用于存储独属于线程的变量，这些变量可以在同一个线程内跨方法、跨类传递。每一个ThreadLocal对象，只能为当前线程关联一个数据，如果要为当前线程关联多个数据，就需要使用多个ThreadLo…...

编程日记 2025/8/24 4:00:42

MuBlE:为机器人操作任务规划提供了逼真的视觉观察和精确的物理建模

2025-03-05，由华为诺亚方舟实验室、捷克技术大学和帝国理工学院联合开发的MuBlE（MuJoCo and Blender simulation Environment）模拟环境和基准测试。通过结合MuJoCo物理引擎和Blender高质量渲染，为机器人操作任务规划提供了逼真的视…...

编程日记 2025/8/24 4:02:34

计算机网络笔记(一)——1.1计算机网络在信息时代中的作用

21世纪的一些重要特征是数字化、网络化和信息化，它是一个以网络为核心的信息时代。要实现信息化就必须依靠完善的网络，因为网络可以迅速地传递信息。网络现在已经成为信息社会的命脉和发展知识经济的重要基础。有三大类网络大家应该很熟悉，即…...

编程日记 2025/8/21 22:18:16

第十五届蓝桥杯省赛电子类单片机学习过程记录（客观题）

客观试题： 01．典型的BUCK电源电路包含哪些关键器件（ABCD） A. 电容 B. 二极管 C. 电感 D. MOSFET 解析：典型的 BUCK 电源电路是一种降压型的直流-直流转换电路，它包含以下关键器件： A.电容：电容在电路中起到滤波的作用。输入电容用于平滑输入电压的波动，减少电源噪声对…...

编程日记 2025/8/23 5:20:59

计算机组成与体系结构-存储系统

主存编址存储单元：最小存储单元，一般为4bit。每个存储单元有自己的二进制编号存储器：多个存储单元排布而成。常见的有8*4存储器（8个4bit的存储单元） 编址内容： 按字编址：存储体的最小存储单…...

编程日记 2025/8/24 4:02:54

better-sqlite3之exec方法

在 better-sqlite3 中，.exec() 方法用于执行包含多个 SQL 语句的字符串。与预编译语句相比，这种方法性能较差且安全性较低，但有时它是必要的，特别是当你需要从外部文件（如 SQL 脚本）中执行多个 SQL 语句时。…...

编程日记 2025/8/16 12:25:22

WinUI 3 支持的三种窗口及受限的窗口透明

我的目标希望能够熟悉 WinUI 3 窗口的基本使用方式，了解可能出现的问题。 WinUI 3 支持三种窗口模式，分别为：常规窗口模式、画中画模式、全屏模式。窗口模式：常规即我们最常见的普通窗口。支持：显示最大化按钮…...

编程日记 2025/8/16 12:33:23

【运维笔记】Navicat中删除mongo 某个时间之前的数据

【运维笔记】Navicat中删除mongo 某个时间之前的数据一、场景与需求1.1、场景1.2、需求二、解决方案三、实战3.1、【Navicat】使用sql语句 （推荐）Step 1：使用查询窗口 - 查询Step 2：确认第一步的数据是否是需要删除的数据Step 3…...

编程日记 2025/8/21 8:21:44

java2025年常见设计模式面试题

1. 请解释建造者模式（Builder Pattern）及其应用场景。答案： 建造者模式用于创建一个复杂的对象，同时允许用户只通过指定复杂对象的类型和内容就能构建它们，隐藏了复杂的构建逻辑。示例： public class C…...

编程日记 2025/8/19 5:43:09

Docker部署Ragflow(完美解决502 bad gateway)

Docker快速启动Ragflow:Dev 系统准备 ubuntu server 24.04 CPU ≥ 4 cores (x86);RAM ≥ 16 GB;Disk ≥ 100 GB; 更新系统 sudo apt update 下载源码 git clone https://github.com/infiniflow/ragflow.git cd ragflow/docker # 切换稳定版本分支 git checkout -f v0.17.…...

编程日记 2025/8/16 11:56:53

算法中的背包问题详解：部分背包与0-1背包

1. 背包问题概述背包问题是组合优化中的经典问题，其核心目标是：在给定容量的背包中装入一组物品，使得物品的总价值最大化。根据物品是否可分割或重复选择，背包问题分为多个变种，其中最常见的两种是： 部分…...

编程日记 2025/8/20 21:39:52

Stream特性（踩坑）：惰性执行、不修改原始数据源

在日常开发中，Stream API 提供了一种高效且易于使用的工具集来处理集合数据。本文主要讲解 Stream 的两个特性：惰性执行，不修改原始数据源。为什么说这两个、而不讲下其他的特性呢？主要是因为在开发中如果忽略这两个特性的话&…...

编程日记 2025/8/18 15:25:37

Varlens（手机上的单反）Ver.1.9.3 高级版.apk

Varlens 是一款专业级手机摄影软件，旨在通过丰富的功能和高自由度参数调节，让手机拍摄效果媲美微单相机。以下是核心功能总结： 一、核心功能专业拍摄模式支持手动/自动/程序模式，可调节ISO、快门速度、EV、白平衡等参数27 提供…...

编程日记 2025/8/20 7:45:18

【无监督学习】层次聚类步骤及matlab实现

层次聚类 （四）层次聚类1.算法步骤2.MATLAB 实现参考资料 （四）层次聚类层次聚类是一种通过逐层合并或分裂数据点构建树状结构（树状图，Dendrogram）的聚类方法。它分为两种类型： 凝聚…...

编程日记 2025/8/23 13:19:52

uploadlabs通关思路

目录靶场准备复现 pass-01 代码审计执行逻辑文件上传方法一：直接修改或删除js脚本方法二：修改文件后缀 pass-02 代码审计文件上传 1. 思路 2. 实操 pass-03 代码审计过程： 文件上传 pass-04 代码审计文件上传 p…...

编程日记 2025/8/22 11:07:12

doris：Elasticsearch

Elasticsearch Catalog 除了支持自动映射 ES 元数据外，也可以利用 Doris 的分布式查询规划能力和 ES(Elasticsearch) 的全文检索能力相结合，提供更完善的 OLAP 分析场景解决方案： ES 中的多 index 分布式 Join 查询。 Doris 和 ES 中的表联合…...

编程日记 2025/8/22 15:29:07

JetBrains学生申请

目录 JetBrains学生免费授权申请 IDEA安装与使用第一个JAVA代码 1.利用txt文件和cmd命令运行 2.使用IDEA新建项目 JetBrains学生免费授权申请本教程采用学生校园邮箱申请，所以要先去自己的学校申请校园邮箱。进入JetBrains官网点击立即申请，然…...

编程日记 2025/8/18 7:40:37

PDFMathTranslate安装使用

PDF全文翻译！！！！ PDFMathTranslate安装使用它是个啥 PDFMathTranslate 可能是一个用于 PDF 文件的数学公式翻译工具。它可能包含以下功能： 提取 PDF 内的数学公式将数学公式转换成 LaTeX 代码翻译数学公式的内…...

编程日记 2025/8/21 14:58:53

清华北大推出的 DeepSeek 教程（附 PDF 下载链接）

清华和北大分别都有关于DeepSeek的分享文档，内容非常全面，从原理和具体的应用，大家可以认真看看。北大 DeepSeek 系列 1：提示词工程和落地场景.pdf　北大 DeepSeek 系列 2：DeepSeek 与 AIGC 应用.pdf　清华 Deep…...

编程日记 2025/8/22 10:38:57

2025-03-09 学习记录--C/C++-PTA 练习11-4 字符定位（最后一次找到的字符）

合抱之木，生于毫末；九层之台，起于累土；千里之行，始于足下。💪🏻 一、题目描述 ⭐️ 裁判测试程序样例： #include <stdio.h> char *match(char *s, char ch); int main(void …...

编程日记 2025/8/16 10:05:45

C语言数据结构之顺序表

目录 1.线性表 2.顺序表 2.1.静态顺序表 2.2.动态顺序表 2.2.1.初始化 2.2.2.清空顺序表 2.2.3.扩容＋尾插 2.2.4.尾出函数 2.2.5.头插函数 2.2.6.头出函数 2.2.7.在中间位置插入 2.2.8.删除中间位置数据 2.2.9.查找函数 2.2.10.总结 3.OJ例题 3.1.合…...

编程日记 2025/8/21 14:13:22

【Git】合并冲突

合并冲突可是，在实际分支合并的时候，并不是想合并就能合并成功的，有时候可能会遇到代码冲突的问题。为了演示这问题，创建一个新的分支 dev1 ，并切换至目标分支，我们可以使用 git checkout -b dev1 一步…...

编程日记 2025/8/23 15:39:44

【每日学点HarmonyOS Next知识】Web跨域资源、Web长按菜单、Web拦截请求、禁止录屏、Base64图片宽高

1、HarmonyOS Web组件本地资源跨域问题？ 关于资源跨域问题的解决，可以参考以下官网文档：https://developer.huawei.com/consumer/cn/doc/harmonyos-guides-V5/web-cross-origin-V5 方法一为了使Web组件能够成功访问跨域资源，开…...

编程日记 2025/8/17 11:29:55