算法基础之二分与前缀和 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…...
OpenLayers 可视化之热力图
注:当前使用的是 ol 5.3.0 版本,天地图使用的key请到天地图官网申请,并替换为自己的key 热力图(Heatmap)又叫热点图,是一种通过特殊高亮显示事物密度分布、变化趋势的数据可视化技术。采用颜色的深浅来显示…...
java_网络服务相关_gateway_nacos_feign区别联系
1. spring-cloud-starter-gateway 作用:作为微服务架构的网关,统一入口,处理所有外部请求。 核心能力: 路由转发(基于路径、服务名等)过滤器(鉴权、限流、日志、Header 处理)支持负…...
日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする
日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...

相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解
【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了: 这一篇我们开始讲: 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下: 一、场景操作步骤 操作步…...
可靠性+灵活性:电力载波技术在楼宇自控中的核心价值
可靠性灵活性:电力载波技术在楼宇自控中的核心价值 在智能楼宇的自动化控制中,电力载波技术(PLC)凭借其独特的优势,正成为构建高效、稳定、灵活系统的核心解决方案。它利用现有电力线路传输数据,无需额外布…...

UE5 学习系列(三)创建和移动物体
这篇博客是该系列的第三篇,是在之前两篇博客的基础上展开,主要介绍如何在操作界面中创建和拖动物体,这篇博客跟随的视频链接如下: B 站视频:s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...

前端开发面试题总结-JavaScript篇(一)
文章目录 JavaScript高频问答一、作用域与闭包1.什么是闭包(Closure)?闭包有什么应用场景和潜在问题?2.解释 JavaScript 的作用域链(Scope Chain) 二、原型与继承3.原型链是什么?如何实现继承&a…...
工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配
AI3D视觉的工业赋能者 迁移科技成立于2017年,作为行业领先的3D工业相机及视觉系统供应商,累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成,通过稳定、易用、高回报的AI3D视觉系统,为汽车、新能源、金属制造等行…...

tree 树组件大数据卡顿问题优化
问题背景 项目中有用到树组件用来做文件目录,但是由于这个树组件的节点越来越多,导致页面在滚动这个树组件的时候浏览器就很容易卡死。这种问题基本上都是因为dom节点太多,导致的浏览器卡顿,这里很明显就需要用到虚拟列表的技术&…...
Device Mapper 机制
Device Mapper 机制详解 Device Mapper(简称 DM)是 Linux 内核中的一套通用块设备映射框架,为 LVM、加密磁盘、RAID 等提供底层支持。本文将详细介绍 Device Mapper 的原理、实现、内核配置、常用工具、操作测试流程,并配以详细的…...