前缀和差分(C/C++)

news/2024/3/29 7:03:20/文章来源:https://blog.csdn.net/m0_73096566/article/details/129129517

目录

1. 前缀和的定义

2. 一维前缀和

2.1 计算公式

2.2 用途

         2.3 小试牛刀 

3. 二维前缀和

3.1 用途


1. 前缀和的定义

对于一个给定的数列A,他的前缀和数中 S 中 S[ i ] 表示从第一个元素到第 i 个元素的总和。

如下图:绿色区域的和就是前缀和数组中的 S [ 6 ]。

 这里你可能就会有一个疑问?为什么是 S[ 6 ] 的位置,而不是 S[ 5 ] 的位置呢??即前缀和组中 S[ 0 ] 并没有参与求和的运算。这里先卖个关子等会在做解释。

2. 一维前缀和

2.1 计算公式

前缀和数组的每一项是可以通过原序列以递推的方式推出来的,递推公式就是:S[ i ] = S[  i - 1 ] + A[ i ]。S[  i - 1 ] 表示前 i - 1 个元素的和,在这基础上加上 A[ i ],就得到了前 i 个元素的和 S [ i ]。

2.2 用途

一维前缀和的主要用途:求一个序列中某一段区间中所有元素的和。有如下例子:

有一个长度为 n 的整数序列。

接下来输入 m 个询问,每个询问输入一对 l,r。

对于每个询问,输出原序列中第 l 个数到第 r 个数的和。

这边是对前缀和的应用,如果用常规的方法:从 l 到 r 遍历一遍,则需要O(N)的时间复杂度。但是有前缀和数组的话,我们可以直接利用公式:sum = S[ r ] - S[ l - 1 ],其中sum是区间中元素的总和,l 和 r 就是区间的边界。下图可帮助理解这个公式。

 当我们要求的是序列 A 的前 n 个数之和时,如果我们是从下标为 0 的位置开始存储前缀和数组,此公式:sum = S[ r ] - S[ l - 1 ] 显然就无法使用了,为了是这个公式适用于所有情况,我们将从下标为 1 的位置开始存储前缀和,并且将下标为 0 的位置初始化为 0。

 

 这便是为什么 S[ 0 ] 并未参与求和的运算。

有了上面的分析我们就能轻松解决这道题啦!

有一个长度为 n 的整数序列。

接下来输入 m 个询问,每个询问输入一对 l,r。

对于每个询问,输出原序列中第 l 个数到第 r 个数的和。

输入格式

第一行包含两个整数n和m。

第二行包含n个整数,表示整数数列。

接下来m行,每行包含两个整数l和r,表示一个询问区间的范围。

void test01()
{//定义数组的大小const int N = 100;//整数序列aint a[N] = { 0 };//存储前缀和的数组s,将全部元素初始化为0,即可达到将s[0]初始化为0的目的int s[N] = { 0 };int n, m;scanf("%d %d", &n, &m);//整数序列的输入for (int i = 1; i <= n; i++){scanf("%d", &a[i]);//读数据的同时利用递推式求前缀和s[i] = s[i - 1] + a[i];}//m个询问while (m--){int l, r;scanf("%d %d", &l, &r);//利用求区间元素个数的通式计算结果printf("%d\n", s[r] - s[l - 1]);}}int main()
{//一维前缀和test01();system("pause");return 0;
}

 2.3 小试牛刀 

原题链接:

209. 长度最小的子数组 - 力扣(LeetCode)icon-default.png?t=N176https://leetcode.cn/problems/minimum-size-subarray-sum/

题目描述:

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组,并返回其长度。如果不存在符合条件的子数组,返回 0 。

3. 二维前缀和

和一维前缀和的原理类似,只不过二维前缀和求的是一个矩阵中所有元素的和。

 例如:对与 x = 4,y = 3 这么一组输入,就是将原矩阵序列中蓝色区域的元素相加,得到的结果便是前缀和矩阵S中 S[ 4 ][ 3 ] 的值。

3.1 用途

一维前缀和求的是某一个区间中所有元素的和,那么二维前缀和就是求一个大矩阵中某个小的矩阵中所有元素的和。

 例如上图:我们要求蓝色矩阵中所有元素的和。

 现在就差最后一步了,怎么求出前缀和矩阵中的每一个值嘞??同理利用递推关系求就阔以啦。

                            S[ i ][ j ] = S[ i - 1 ][ j ] + S[ i ][ j - 1 ] - S[ i - 1][ j - 1 ] + a[ i ][ j ]

其中a为原矩阵序列。可以尝试举一个具体的例子来理解。

有了以上知识,我们可以尝试写代码求一下。

输入一个n行m列的矩阵,在输入q个询问,每个询问包含四个整数x1,y1,x2,y2,表示一个子矩阵左上角的坐标和右下角的坐标。

对于每个询问输出子矩阵中所有数的和。

输入格式

第一行包含三个整数n,m,q

接下来n行,每行包含m个整数,表示整数矩阵。

接下来q行,每行包含四个整数x1,y1,x2,y2,表示一组询问。

void test02()
{//定义数组的大小const int N = 100;//原矩阵序列aint a[N][N] = { 0 };//前缀和矩阵,同样需要初始化为0,原因同一维矩阵int s[N][N] = { 0 };//读入一个n * m 的矩阵int n, m, q;scanf("%d %d %d", &n, &m, &q);for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){scanf("%d", &a[i][j]);//读入矩阵的同时求前缀和s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];}}//q个询问while (q--){int x1, y1, x2, y2;scanf("%d %d %d %d", &x1, &y1, &x2, &y2);//利用前面推导过的公式直接打印数据即可printf("%d\n", s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]);}printf("\n");
}int main()
{//二维前缀和test02();system("pause");return 0;
}

 

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_71745.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

清洁级动物(CL)实验室设计SICOLAB

清洁级动物&#xff08;CL&#xff09;实验室设计清洁级动物&#xff08;CL&#xff09;实验室设计有哪些内容&#xff1f;工艺流程是如何&#xff1f;功能房间的划分清洁级动物实验室&#xff08;CL实验室&#xff09;是进行高洁净度动物实验的专门场所&#xff0c;需要满足一…

Shopee、ebay、亚马逊等跨境卖家了解测评的一篇干货

随着时代的发展&#xff0c;大家越来越喜欢网购&#xff0c;国外也有亚马逊、沃尔码、阿里国际、速卖通、ebay、shopee、Lazada、ozon、temu等等&#xff0c;而国外这些平台也有很大的市场&#xff0c;跨境电商也随时诞生&#xff0c;而当今社会环境实体生意越来越难做&#xf…

Kubernetes二 Kubernetes之实战以及pod详解

Kubernetes入门 一 Kubernetes实战 本章节将介绍如何在kubernetes集群中部署一个nginx服务&#xff0c;并且能够对其进行访问。 1.1 Namespace Namespace是kubernetes系统中的一种非常重要资源&#xff0c;它的主要作用是用来实现多套环境的资源隔离或者多租户的资源隔离。…

【java】Spring Cloud --Spring Cloud 的核心组件

文章目录前言一、Eureka&#xff08;注册中心&#xff09;二、Zuul&#xff08;服务网关&#xff09;三、 Ribbon&#xff08;负载均衡&#xff09;四、Hystrix&#xff08;熔断保护器&#xff09;五、 Feign&#xff08;REST转换器&#xff09;六、 Config&#xff08;分布式配…

飞塔Fortinet防火墙SSL VPN双因素身份认证(2FA)方案

作为行业领先的防火墙厂商&#xff0c;飞塔Fortinet结合了高性能 VPN 功能&#xff0c;代表了网络安全的新概念。其中飞塔Fortinet防火墙 SSL VPN 因其突出的安全性能而被广泛应用在远程办公场景中。但在 SSL VPN 登录时用户仅需输入用户名和固定的静态密码&#xff0c;若遭遇账…

kettle安装部署_简单认识_Spoon勺子界面---大数据之kettle工作笔记002

然后我们来看一下这个kettle的安装,很简单,下载解压就可以了 上面的地址是官网很烂 下面的地址好一些 这个是官网可以看到很慢,很不友好 这个是下面那个地址,可以看到 最新的是9.0了,一般都用 一般都用8.2 这里下载这个就可以了 下载以后可以看到有个pdi

LeetCode 每日一题2347. 最好的扑克手牌

Halo&#xff0c;这里是Ppeua。平时主要更新C语言&#xff0c;C&#xff0c;数据结构算法......感兴趣就关注我吧&#xff01;你定不会失望。 &#x1f308;个人主页&#xff1a;主页链接 &#x1f308;算法专栏&#xff1a;专栏链接 我会一直往里填充内容哒&#xff01; &…

《爆肝整理》保姆级系列教程python接口自动化(十九)--Json 数据处理---实战(详解)

简介 上一篇说了关于json数据处理&#xff0c;是为了断言方便&#xff0c;这篇就带各位小伙伴实战一下。首先捋一下思路&#xff0c;然后根据思路一步一步的去实现和实战&#xff0c;不要一开始就盲目的动手和无头苍蝇一样到处乱撞&#xff0c;撞得头破血流后而放弃了。不仅什么…

【大数据离线开发】7.2 搭建HBase环境

7.2 搭建HBase的环境 准备工作&#xff1a; 解压Hbase安装包 [rootbigdata111 tools]# tar -zxvf hbase-1.3.1-bin.tar.gz -C ~/training/设置Hadoop的环境变量 vi ~/.bash_profile HBASE_HOME/root/training/hbase-1.3.1 export HBASE_HOMEPATH$HBASE_HOME/bin:$PATH export…

005 利用fidder抓取app的api,获得股票数据

一、下载安装fidder 百度搜索fidder直接下载&#xff0c;按提示安装即可。 二、配置fidder 1. 打开fidder&#xff0c;选择tools——options。 2. 选择HTTPS选项卡&#xff0c;勾选前三项&#xff0c;然后点击右侧【actions】&#xff0c;选择【trust root certificate】&a…

黑马程序员-Linux系统编程-01

课程链接 01-Linux命令基础习惯-Linux系统编程_哔哩哔哩_bilibili 课程重点笔记 01-linux命令基础习惯 终端 终端&#xff1a;一切输入、输出的总称&#xff0c;因此终端并不是一定指的是命令行&#xff0c;只要是能进行输入或者输出即可&#xff0c;但是在linux终端上‘’内…

Java EE|TCP/IP协议栈之传输层UDP协议详解

文章目录一、对UDP协议的感性认识简介主要特点二、UDP的报文结构协议端格式概览报文结构详解源端口目的端口16位UDP报文长度16位校验和参考一、对UDP协议的感性认识 简介 UDP&#xff0c;是User Datagram Protocol的简称&#xff0c;中文名是用户数据报协议&#xff0c;是OSI…

RocketMQ 第二章

RocketMQ 第二章 7、SpringBoot整合RocketMQ SpringBoot 提供了快捷操作 RocketMQ 的 RocketMQTemplate 对象。 7.1、引入依赖 注意依赖的版本需要和 RocketMQ 的版本相同。 <dependency><groupId>org.apache.rocketmq</groupId><artifactId>rock…

【Java期末复习】《面向对象程序设计》练习库

目录 一、单选题 二、填空题 三、程序填空题 1、 super使用--有如下父类和子类的定义&#xff0c;根据要求填写代码 2、简单加法计算器的实现 3、House类 4、矩形类 5、创建一个Box类&#xff0c;求其体积 四、函数题 6-1 求圆面积自定义异常类 6-2 判断一个数列是…

会利用信息差赚钱的人才是聪明人

毕业后找不到工作&#xff0c;穷到只剩下时间&#xff0c;大小做了20多份副业兼职&#xff0c;终于找到了可靠的渠道&#xff0c; 我是专科生&#xff0c;学历不好&#xff0c;专业拉胯。毕业后&#xff0c;我找了两三份工作。要么工资太低&#xff0c;只能交房租&#xff0c;…

一种基于强化学习的自动变道机动方法

文章目录摘要前言相关的工作方法论动作空间奖励函数设计Q学习仿真结果结论摘要 变道是一项至关重要的车辆操作&#xff0c;需要与周围车辆协调。建立在基于规则的模型上的自动换道功能可能在预定义的操作条件下表现良好&#xff0c;但在遇到意外情况时可能容易失败。在我们的研…

python元类编程

1.1.propety动态属性 在面向对象编程中&#xff0c;我们一般把名词性的东西映射成属性&#xff0c;动词性的东西映射成方法。在python中他们对应的分别是属性self.xxx和类方法。但有时我们需要的属性需要根据其他属性动态的计算&#xff0c;此时如果直接使用属性方法处理&…

vulnhub zico2

总结&#xff1a;脏牛提权 目录 下载地址 漏洞分析 信息收集 木马上传 反弹shell 提权 下载地址 zico2.ova (Size: 828 MB)Download: https://www.dropbox.com/s/dhidaehguuhyv9a/zico2.ovaDownload (Mirror): https://download.vulnhub.com/zico/zico2.ova使用方法&…

16_FreeRTOS队列集

目录 队列集 队列集相关API函数介绍 队列集使用流程 实验源码 队列集 一个队列只允许任务间传递的消息为同一种数据类型,如果需要在任务间传递不同数据类型的消息时,那么就可以使用队列集! 作用:用于对多个队列或信号量进行“监听”其中不管哪一个消息到来&#xff0c;都…

jQuery.NiceScroll - 有史以来最好的 nicescroll 版本——在现代浏览器和移动设备上极其流畅和一致,资源使用率低(中文文档)

jQuery.NiceScroll特征依赖关系使用配置参数有史以来最好的 nicescroll 版本——在现代浏览器和移动设备上极其流畅和一致&#xff0c;资源使用率低 官网:nicescroll.areaaperta.com GitHub:github.com/inuyaksa/jquery.nicescroll CDN引入: https://www.bootcdn.cn/jquery.nic…