算法基础之二分与前缀和 day 6
文章目录
- 二分
- 第一类
- 第二类
- 前缀和
- 原题链接
- 题目描述
- 输入格式
- 输出格式
- 数据范围
- 输入样例:
- 输出样例:
- 题目分析
- 示例代码
二分
二分法是我们在高中数学就学习过的一种思想,他也是一种效率较高的查找算法,在编写代码的过程中,初学者很容易就会陷入死循环
二分的基本步骤如下
第一步是需要确定一个区间,使得我们的目标值一定是在区间中出现的
第二步需要确定一个性质,使得这个性质满足两点,第一点是可以根据这个性质把这个区间分为左和右连续的两段,第二点是我们最终的答案一定是二分的某一个分界点(绝大多数)
整数二分是很容易出现死循环的一种情况,因为整数是离散的,因此对应的答案在边界的情况也是两种
其实相对应的,我们也可以将二分分为两大类,一种是答案在左边的终点,另一种是答案在右边的起点
我们来具体看一下这两种问题是如何二分的
第一类
目标值在红色区间的右端点
我们把区间进行标注,如图
M是L和R的中点,其实就把区间[L,R]分成[L,M-1]和[M,R]
分成两段之后,我们只需要判断M的颜色(性质),如果是在红色区间,就说明目标值一定在绿色区间[M,R]内,否则说明目标值在红色区间[L,M-1]内
对应到代码上,我们可以这样写
while (L < R)
{M = (L + R + 1) / 2;if (M == '红')L = M;elseR = M - 1;
}
这里需要注意的就是,当答案在左边区间的最后一位时,由于C/C++会自动下取整,这里算中点时就需要补上1,这样就不会漏判(死循环)了,当然这里也可以更改判断条件(例如L<=R),同样也不会出现死循环
这里有个简单的判断是否需要补上1,就是看我们在判断的时候如果写的是L=M,加上1就可以了
第二类
目标值是绿色区间的左端点
将[L,R]分成[L,M]和[M+1,R],如果M是绿色,说明目标值在红色区间[L,M],否则就是在绿色区间[M+1,R]
这里我们可以给出相应的代码
while (L < R)
{M = (L + R) / 2;if (M == '绿')R = M;elseL = M + 1;
}
同样的,我们也是只要看判断之后的赋值语句即可,当L = M时,则需要加上1,当R = M时,则不需要加
前缀和
前缀和其实是一种快捷的求和的思想,是用于求一个静态区间的任意位置之间的所有数的和的思想
这里我们直接结合最基础的例题来理解
原题链接
795. 前缀和
题目描述
输入一个长度为 n 的整数序列。
接下来再输入 m 个询问,每个询问输入一对 l,r。
对于每个询问,输出原序列中从第 l 个数到第 r 个数的和。
输入格式
第一行包含两个整数 n 和 m。
第二行包含 n 个整数,表示整数数列。
接下来 m 行,每行包含两个整数 l 和 r,表示一个询问的区间范围。
输出格式
共 m 行,每行输出一个询问的结果。
数据范围
1≤l≤r≤n,
1≤n,m≤100000,
−1000≤数列中元素的值≤1000
输入样例:
5 3
2 1 3 6 4
1 2
1 3
2 4
输出样例:
3
6
10
题目分析
这里就是给出一个静态序列,有m次询问,每次给一对l和r,需要分别输出从l到r的总和
如果我们暴力做的话,就是每一次都需要从l加到r,并且每一次循环都是O(n)的时间复杂度
一旦当询问次数较大时,时间效率就会非常低
那么这时我们就会需要用到前缀和的思想,他非常的基础和重要,也是笔者最先开始学习的算法之一
我们把之前的那个静态序列标记为 a i a_i ai,表示第i项,然后我们来构建一个新的序列 s i s_i si,代表他是原序列中前i个数字的和
其中 s i = a 1 + a 2 + ⋯ + a i s_i = a_1 + a2 + \dots + a_i si=a1+a2+⋯+ai
特殊规定 s 0 = 0 s_0 = 0 s0=0
这样我们就可以发现一个规律
s i = s i − 1 + a i s_i = s_{i-1} + a_i si=si−1+ai
我们可以根据这个公式递推出s序列中的所有数字
for(int i = 1; i <= n; i++)
{s[i] = s[i-1] + a[i];
}
这一步骤就叫做前缀和,也是我们之后求和的预处理工作
当我们想算从l到r的和时可以这样 a l + a l + 1 + a l + 2 + ⋯ + a r a_l + a_{l+1} + a_{l+2} + \dots + a_r al+al+1+al+2+⋯+ar
= a 1 + a 2 + ⋯ + a l − 1 + a l + a l + 1 + a l + 2 + ⋯ + a r − a 1 − a 2 − ⋯ − a l − 1 = a_1 + a_2 + \dots + a_{l-1} + a_l + a_{l+1} + a_{l+2} + \dots + a_r - a_1 - a_2 - \dots - a_{l-1} =a1+a2+⋯+al−1+al+al+1+al+2+⋯+ar−a1−a2−⋯−al−1
= s r − s l − 1 = s_r - s_{l-1} =sr−sl−1
所以当我们预处理结束之后,我们只需要计算两个数的差即可,这样的时间复杂度就达到了O(1),是质的飞跃
对于计算区间和还有其他的方法,例如树状数组和线段树,这个我们以后会讲解,而对于前缀和来说,他的局限性就在于序列只能是静态的序列,一旦其中的某个数值被修改,就需要重新计算前缀和,而树状数组和线段树是可以实现边查边算的
示例代码
#include<iostream>
using namespace std;const int N = 1e5+10; // 数据范围
int n,m;
long long arr[N]; // 原数组
long long pre[N]; // 前缀和数组int main()
{cin >> n >> m;for(int i=1;i<=n;i++) // 数据输入{cin>>arr[i];pre[i] = pre[i-1] + arr[i]; // 前缀和初始化}while(m--){int l,r;cin>>l>>r;cout<<pre[r] - pre[l-1]<<'\n';}return 0;
}
相关文章:

算法基础之二分与前缀和 day 6
文章目录 二分第一类第二类 前缀和原题链接题目描述输入格式输出格式数据范围输入样例:输出样例: 题目分析示例代码 二分 二分法是我们在高中数学就学习过的一种思想,他也是一种效率较高的查找算法,在编写代码的过程中࿰…...

github短视频去除水印项目Douyin_TikTok_Download_API介绍
当下正值短视频盛行的时代。在我们浏览短视频的同时,经常能发现一些精美的图片、引人入胜的文案以及吸引眼球的视频,想要将它们保存到本地。然而,保存下来的图片或视频通常伴随着不太愉悦的水印,这显著降低了使用体验。因此&#…...

FindMy技术用于键盘
键盘是我们生活中不可或缺的输入工具,是人与计算机之间沟通的桥梁,无论是编写文档、浏览网页、玩游戏、或是进行复杂的数据分析,键盘都在其中发挥着关键的作用。此外,键盘还是各种软件的快捷键操作的关键。通过熟练地运用快捷键&a…...

认识jmeter接口测试工具!
jmeter简介 Apache JMeter是Apache组织开发的基于Java的压力测试工具。用于对软件做压力测试,它最初被设计用于Web应用测试,但后来扩展到其他测试领域。 下载 下载地址:Apache JMeter - Download Apache JMeter 安装 由于Jmeter…...
强大的按钮类CButtonST
转自:哈哈 强大的CButtonST_cbuttonst demo-CSDN博客 这里给大家介绍强大的按钮类CButtonST,可以使您的程序锦上添花。 CButtonST类主要包括BtnST.h、BtnST.cpp、BCMenu.h和BCMenu.cpp四个文件。先将上述4个文件复制到自己的工程,然后在VC开…...
学习ing
记录 1.光圈的大小由一个称为“F值”的数字表示,这个数字越小,光圈就越大,光线也就越多。一般来说,使用较小的F值可以拍摄出更亮的照片,而使用较大的F值可以拍摄出更暗的照片。 2.光圈可以控制相机的曝光时间&#x…...
linux下数据库定时备份
1.编写shell脚本 #!/bin/bash USER"root" PASSWORD"Root.36#336" DATABASE"backup_test" HOSTNAME"127.0.0.1" DATEdate %Y%m%d_%H%M%S #日期格式(作为文件名) BACKUP_DIR/home/mysql/DB_backup/ #备份文件存…...

Qt/QML编程学习之心得:QSocketNotifier(二十一)
QSocketNotifier在Qt中怎么使用? QSocketNotifier使Qt的事件循环与其他基于文件描述符的事件循环集成成为可能。在Qt的主事件循环(QCoreApplication::exec())中检测到文件描述符操作。 使用低级(通常是特定于平台的)API打开设备后,可以创建一个套接字通知程序来监视文…...

【linux】lsblk和df -h显示的磁盘信息不同
【问题分析】 lsblk 查看的是block device,也就是逻辑磁盘大小。 df查看的是file system, 也就是文件系统层的磁盘大小。 这种情况应该是block device容量变大,单还没有反映到file system中。 【问题解决】 如果是ext{2,3,4}文件系统的话,可以用res…...
如何开发属于自己的小程序?
随着移动互联网的快速发展,小程序已成为一种不可忽视的力量。对于许多企业和个人而言,拥有一个属于自己的小程序不仅能提高品牌曝光度,还能带来实实在在的收益。那么,如何开发属于自己的小程序呢?本文将为你揭秘这一过…...

湖仓架构的演进
1.数据仓库架构的历史演进 起初,业界数据处理首选方式是数仓架构。通常数据处理的流程是把一些业务数据库,通过ETL的方式加载到Data Warehouse中,再在前端接入一些报表或者BI的工具去展示。 数据仓库概念是 Inmon 于 1990 年提出并给出了完…...
【头歌实训】Spark MLlib ( Python 版 )
文章目录 第1关:基本统计编程要求测试说明答案代码 第2关:回归编程要求测试说明参考资料答案代码 第3关:分类编程要求测试说明参考资料答案代码 第4关:协同过滤编程要求测试说明参考资料答案代码 第5关:聚类编程要求测…...

Java基础进阶(学习笔记)
注:本篇的代码和PPT图片来源于黑马程序员,本篇仅为学习笔记 static static 是静态的意思,可以修饰成员变量,也可以修饰成员方法 修饰成员的特点: 被其修饰的成员, 被该类的所有对象所共享 多了一种调用方式, 可以通过…...
uView NoticeBar 滚动通知
该组件用于滚动通告场景,有多种模式可供选择 #平台差异说明 App(vue)App(nvue)H5小程序√√√√ #基本使用 通过text参数设置需要滚动的内容 <template><view><u-notice-bar :text"text1&quo…...

外包干了3个多月,技术退步明显。。。。。
先说一下自己的情况,本科生生,19年通过校招进入广州某软件公司,干了接近4年的功能测试,今年年初,感觉自己不能够在这样下去了,长时间呆在一个舒适的环境会让一个人堕落!而我已经在一个企业干了四年的功能测…...
JSON的一些资源
以下是一些推荐的学习资源: 1. **官方网站**: - JSON.org: 这是一个很好的起点,它提供了JSON的基本介绍和语法规则。 2. **在线教程和课程**: - CSDN全方面学习各种资源。 - W3Schools (w3schools.com): 提供了一个关于JSON的教程,涵…...
最优化理论期末复习笔记 Part 1
数学基础线性代数 从行的角度从列的角度行列式的几何解释向量范数和矩阵范数 向量范数矩阵范数的更强的性质的意义 几种向量范数诱导的矩阵范数 1 范数诱导的矩阵范数无穷范数诱导的矩阵范数2 范数诱导的矩阵范数 各种范数之间的等价性向量与矩阵序列的收敛性 函数的可微性与展…...

鸿蒙应用中的通知
目录 1、通知流程 2、发布通知 2.1、发布基础类型通知 2.1.1、接口说明 2.1.2、普通文本类型通知 2.1.3、长文本类型通知 2.1.4、多行文本类型通知 2.1.5、图片类型通知 2.2、发布进度条类型通知 2.2.1、接口说明 2.2.2、示例 2.3、为通知添加行为意图 2.3.1、接…...
如何停止一个运行中的Docker容器
要停止一个运行中的Docker容器,你可以使用以下命令: docker stop <容器ID或容器名> 将 <容器ID或容器名> 替换为你要停止的具体容器的标识符或名称。你可以使用以下命令查看正在运行的容器:docker ps 这将列出所有正在运行的…...

Linux第19步_安装“Ubutun交叉编译工具链”
由于Ubuntu系统使用的GCC编译器,编译结果是X86文件,只能在X86上运行,不能在ARM上直接运行。因此,还要安装一个“Ubutun交叉编译工具链”,才可以在ARM上运行。 arm-none-linux-gnueabi-gcc是 Codesourcery 公司&#x…...
脑机新手指南(八):OpenBCI_GUI:从环境搭建到数据可视化(下)
一、数据处理与分析实战 (一)实时滤波与参数调整 基础滤波操作 60Hz 工频滤波:勾选界面右侧 “60Hz” 复选框,可有效抑制电网干扰(适用于北美地区,欧洲用户可调整为 50Hz)。 平滑处理&…...

微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】
微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来,Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...
java 实现excel文件转pdf | 无水印 | 无限制
文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...

剑指offer20_链表中环的入口节点
链表中环的入口节点 给定一个链表,若其中包含环,则输出环的入口节点。 若其中不包含环,则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...

PL0语法,分析器实现!
简介 PL/0 是一种简单的编程语言,通常用于教学编译原理。它的语法结构清晰,功能包括常量定义、变量声明、过程(子程序)定义以及基本的控制结构(如条件语句和循环语句)。 PL/0 语法规范 PL/0 是一种教学用的小型编程语言,由 Niklaus Wirth 设计,用于展示编译原理的核…...
Rust 异步编程
Rust 异步编程 引言 Rust 是一种系统编程语言,以其高性能、安全性以及零成本抽象而著称。在多核处理器成为主流的今天,异步编程成为了一种提高应用性能、优化资源利用的有效手段。本文将深入探讨 Rust 异步编程的核心概念、常用库以及最佳实践。 异步编程基础 什么是异步…...

图表类系列各种样式PPT模版分享
图标图表系列PPT模版,柱状图PPT模版,线状图PPT模版,折线图PPT模版,饼状图PPT模版,雷达图PPT模版,树状图PPT模版 图表类系列各种样式PPT模版分享:图表系列PPT模板https://pan.quark.cn/s/20d40aa…...

JVM 内存结构 详解
内存结构 运行时数据区: Java虚拟机在运行Java程序过程中管理的内存区域。 程序计数器: 线程私有,程序控制流的指示器,分支、循环、跳转、异常处理、线程恢复等基础功能都依赖这个计数器完成。 每个线程都有一个程序计数…...

2025年渗透测试面试题总结-腾讯[实习]科恩实验室-安全工程师(题目+回答)
安全领域各种资源,学习文档,以及工具分享、前沿信息分享、POC、EXP分享。不定期分享各种好玩的项目及好用的工具,欢迎关注。 目录 腾讯[实习]科恩实验室-安全工程师 一、网络与协议 1. TCP三次握手 2. SYN扫描原理 3. HTTPS证书机制 二…...

使用SSE解决获取状态不一致问题
使用SSE解决获取状态不一致问题 1. 问题描述2. SSE介绍2.1 SSE 的工作原理2.2 SSE 的事件格式规范2.3 SSE与其他技术对比2.4 SSE 的优缺点 3. 实战代码 1. 问题描述 目前做的一个功能是上传多个文件,这个上传文件是整体功能的一部分,文件在上传的过程中…...