【优选算法】Prefix-Kage:前缀和的算法影(上)

文章目录

  • 1.概念解析
  • 2.代码实现
    • 2.1【模版】前缀和(一维)
      • 2.1.1 原理
      • 2.1.2 代码实现
    • 2.2【模版】前缀和(二维)
      • 2.2.1 原理
      • 2.2.2 代码实现
  • 希望读者们多多三连支持
  • 小编会继续更新
  • 你们的鼓励就是我前进的动力!

本篇是优选算法之 前缀和算法,该算法主要用于 代替特定情况下的数组遍历,降低时间复杂度,提高程序效率🚀

1.概念解析

🚩什么是前缀和算法?
前缀和算法是一种用于高效计算数组区间和的算法。对于一个给定的数组 nums,我们可以预先计算出它的前缀和数组 prefixSum ,其中 prefixSum[i] 表示 nums[0]nums[i]元素之和

比如:

数组:
nums [ 1,2,3,4,5,6]
前缀和数组 :
prefixSum [1, 1 + 2, 1 + 2 + 3, 1 + 2 + 3 + 4, 1 + 2 + 3 + 4 + 5]
[1, 3, 6, 10, 15]

🚩为什么要使用前缀和算法?
假设我们要对数组的一块区间进行检查元素个数为 n检查次数为 q ,那么如果使用传统的暴力解法,即模拟算法,每次检查就要遍历一次数组,那么时间复杂度为 O(n∗q),即 O(n²);使用了前缀和算法可以让时间复杂度降级,即O(n) + O(q) ,是一种空间换时间的算法。此时如果 n 和 q 的数据庞大,暴力解法的效率必然是低下的,所以前缀和算法使用是必要的

2.代码实现

2.1【模版】前缀和(一维)

✏️题目描述:

在这里插入图片描述

✏️示例:

在这里插入图片描述

传送门:【模版】前缀和(一维)

2.1.1 原理

💻第一步: 预处理一个前缀和数组

假设有一个数组 arrdp [i] 表示 [1,i] 区间內所有元素的和index 表示数组下标(从 1 开始)
请添加图片描述
每一位的元素都可以表示为 dp[i] = dp[i - 1] + arr[i],即该位元素的和等于前面元素的和加上该位的元素,可能你会无法理解,但本质上是个小的动态规划,会从最开始的元素不断迭代到当前的元素

💻第二步: 使用前缀和数组

那么回到这道题目,我们要求一段区间内的和

请添加图片描述
假设我们要求区间 [3,5] 的数据和,因为前缀和都是从 1 开始加的,所以我们可以用区间 [1,5] 减去 区间[1,2] 得到想要的区间。取左边界为 L右边界为 R,即可总结出公式:某区间的和 = dp[R] - dp[L- 1]

💻细节问题:

为什么 dp 数组从下表为 1 开始?

请添加图片描述
目的是为了添加一个虚拟节点(辅助节点)规避了边界处理的问题。如图所示,如果取区间 [0,2] ,那么左边界 L 取 0 的时候会造成下标为 -1 的情况出现,所以为了避免这种情况,下标从 1 开始存放数据,且下标为 0 处存放数据为 0 就不会影响加和的结果

2.1.2 代码实现

#include <iostream>
#include <vector>
using namespace std;

int main()
{
	//1.读入数据
	int n = 0, q = 0;
	cin >> n >> q;
	vector<int> arr(n + 1, 0);
	for (int i = 1; i <= n; ++i)
	{
		cin >> arr[i];
	}
	//2.预处理出来一个前缀和数组
	vector<long long> dp(n + 1, 0);
	for (int i = 1; i <= n; ++i)
	{
		dp[i] = dp[i - 1] + arr[i];
	}
	//3.使用前缀和数组
	int L = 0, R = 0;
	while (q--)
	{
		cin >> L >> R;
		cout << dp[R] - dp[L - 1] << endl;
	}
	return 0;
}

🔥值得注意的是: dp 数组的容量大小类型应为 long long ,因为存放的数据可能很大,想加后可能会超过 int 的类型大小

2.2【模版】前缀和(二维)

✏️题目描述:

在这里插入图片描述

✏️示例:

在这里插入图片描述

传送门:【模版】前缀和(二维)

2.2.1 原理

根据示例 1 ,二维矩阵图如下:
请添加图片描述
从一点(x1,y1)(x2,y2)的表示这个矩阵中所有元素的和
请添加图片描述
💻第一步: 预处理一个前缀和矩阵

根据题意我们想要求整个矩阵中某个子集矩阵,需要先把求矩阵的模版列出来
所以我们定义 dp[i][j] 表示从 [1,1][i,j] 位置,这段区间里所有元素的和
然后把矩阵划分为A、B、C、D四个部分便于求和

请添加图片描述

显然整个矩阵的面积是由四个部分加和而成,但是我们发现B、C的面积不好求得
所以可以进行一些加减的转化

请添加图片描述

主要是一个矩阵要在[1,1] 位置延伸就比较好算,所以通常会结合着 A 计算,多出的 A 要注意减掉,就可以整理出公式:dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + arr[i][j] - dp[i - 1][j - 1]

💻第二步: 使用前缀和矩阵

回到题目,我们是要求矩阵中某个子集矩阵,所以根据图形及题意,画出如图:

请添加图片描述

还是和第一步的方法一样,巧用加减法算出矩阵元素和

请添加图片描述
那么可以整理出(x1,y1)(x2,y2)表示为 dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1],记得要加上多减的一块 A

2.2.2 代码实现

#include <iostream>
#include <vector>
using namespace std;

int main()
{
	//1.读入数据
	int n = 0, m = 0, q = 0;
	cin >> n >> m >> q;
	vector<vector<int>> arr(n + 1, vector<int>(m + 1));
	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= m; ++j)
		{
			cin >> arr[i][j];
		}
	}
	//2.预处理前缀和矩阵
	vector<vector<long long>> dp(n + 1, vector<long long>(m + 1));
	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= m; ++j)
		{
			dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + arr[i][j] - dp[i - 1][j - 1];
		}
	}
	//3.使用前缀和矩阵
	int x1 = 0, x2 = 0, y1 = 0, y2 = 0;
	while (q--)
	{
		cin >> x1 >> y1 >> x2 >> y2;
		cout << dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1] << endl;
	}
	return 0;
}

🔥值得注意的是: 和一维一样从下标为 1 开始读入数据,用 long long 容器存放

希望读者们多多三连支持

小编会继续更新

你们的鼓励就是我前进的动力!

请添加图片描述

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

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

相关文章

CVE-2024-32709 WordPress —— Recall 插件存在 SQL 注入漏洞

漏洞描述 WordPress 是一款免费开源的内容管理系统,适用于各类网站,包括个人博客、电子商务系统、企业网站。其插件 WP-Recall 的 account 存在 SQL 注入漏洞,攻击者可以通过该漏洞获取数据库敏感信息。 WP-Recall 版本 <= 16.26.5 漏洞复现 搭建环境、安装插件、完成…

网络安全概论——虚拟专网VPN技术

一、VPN概述 1、VPN的概念 所谓虚拟专网&#xff08;Virtual Private Network VPN&#xff09;是指将物理上分布在不同地点的网络通过公用网络连接而构成逻辑上的虚拟子网&#xff0c;它采用认证、访问控制、机密性、数据完整性等安全机制在公用网络上构建专用网络。 如何理…

mobilenetv2-inceptionv3-resnet50三大模型对比实现人脸识别反欺诈系统【带UI界面】

完整项目包获取→点击文章末尾名片&#xff01; 关于数据集&#xff1a;超大规模人脸欺诈数据集。共70多G。 关于模型对比&#xff1a; inceptionv3&#xff1a; mobilenetv2&#xff1a; resnet50&#xff1a; 关于系统&#xff1a; 界面&#xff1a;

十一、e2studio VS STM32CubeIDE之宏函数展开

目录 一、概述/目的 二、复杂宏函数举例 三、编译-预处理 四、stm32cubeide和e2studio的预处理 五、source insight和vscode 一、概述/目的 复杂宏函数如何快速展开 二、复杂宏函数举例 #define R_BSP_MODULE_START(ip, channel) {FSP_CRITICAL_SECTION_DEFI…

FreeRTOS的任务调度

1.启动任务调度器 vTaskStartScheduler void vTaskStartScheduler( void ) { BaseType_t xReturn;/* Add the idle task at the lowest priority. */#if ( INCLUDE_xTaskGetIdleTaskHandle 1 ){/* Create the idle task, storing its handle in xIdleTaskHandle so it canbe …

【Java基础面试题024】Java中包装类型和基本类型的区别是什么?

回答重点 基本类型&#xff1a; Java中有8种基本数据类型&#xff08;byte、short、int、long、float、double、char、boolean&#xff09;他们是直接存储数值的变量&#xff0c;位于栈上&#xff08;局部变量在栈上、成员变量在堆上&#xff0c;静态字段/类在方法区&#xf…

SpringBoot3+Vue3开发在线考试系统

项目介绍 项目分为3种角色&#xff0c;分别为&#xff1a;超级管理员、老师、学生。超级管理员&#xff0c;负责系统的设置、角色的创建、菜单的管理、老师的管理等功能&#xff0c;也可以叫做系统管理员&#xff1b;老师角色&#xff0c;负责系统业务的管理&#xff0c;包括学…

第3节 测试套件数据驱动

创建Excel、 CSV测试数据 1. 从主菜单中选择 File > New > Test Data。将显示新的测试数据对话框。输入测试数据的名称并选择数据类型作为Excel File/ CSV File 。单击OK。 2. 浏览到要导入Katalon Studio的Excel File, 选择Excel中的sheetName&#xff0c;或者CSV文件…

跨站点请求伪造(Cross Sites Request Forgery)类漏洞攻击方式与防御措施|软件安全测试技术系列

本系列文章分享JavaScript语言常见的安全漏洞&#xff0c;漏洞的原理&#xff0c;可能导致的安全问题&#xff0c;以及如何防御与避免。本文分享的是跨站点请求伪造&#xff08;Cross Sites Request Forgery&#xff09;。 跨站点请求伪造&#xff0c;指利用用户身份操作用户账…

【图像分类实用脚本】数据可视化以及高数量类别截断

图像分类时&#xff0c;如果某个类别或者某些类别的数量远大于其他类别的话&#xff0c;模型在计算的时候&#xff0c;更倾向于拟合数量更多的类别&#xff1b;因此&#xff0c;观察类别数量以及对数据量多的类别进行截断是很有必要的。 1.准备数据 数据的格式为图像分类数据集…

飞牛os使用ddns-go配合华为云实现内网穿透

DDNS-Go 是一个开源的动态域名解析工具&#xff0c;它支持多种操作系统&#xff0c;包括 Windows、Mac 和 Linux&#xff0c;并且支持 ARM 和 x86 架构。以下是使用 DDNS-Go 的基本步骤&#xff1a; 1. 下载和安装&#xff1a; 访问 DDNS-Go 的 GitHub 仓库&#xff08;&#x…

易语言OCR证件照文字识别

一.引言 文字识别&#xff0c;也称为光学字符识别&#xff08;Optical Character Recognition, OCR&#xff09;&#xff0c;是一种将不同形式的文档&#xff08;如扫描的纸质文档、PDF文件或数字相机拍摄的图片&#xff09;中的文字转换成可编辑和可搜索的数据的技术。随着技…

二八(vue2-04)、scoped、data函数、父子通信、props校验、非父子通信(EventBus、provideinject)、v-model进阶

1. 组件的三大组成部分(结构/样式/逻辑) 1.1 scoped 样式冲突 App.vue <template><!-- template 只能有一个根元素 --><div id"app"><BaseOne></BaseOne><BaseTwo></BaseTwo></div> </template><script…

3D工具显微镜的测量范围

一、测量尺寸范围 样品尺寸&#xff1a; 3D工具显微镜通常能够测量各种尺寸和形状的样品&#xff0c;从小至微米级别的微小结构到大至几厘米甚至更大的物体。具体的测量尺寸范围取决于显微镜的载物台大小、镜头焦距以及软件处理能力。测量精度&#xff1a; 3D工具显微镜的测量…

C#—扩展方法

扩展方法 扩展方法是C#中一种特殊的静态方法&#xff0c;它定义在一个静态类中&#xff0c;但是可以像实例方法一样被调用&#xff0c;使得代码看起来更为直观和易于阅读。扩展方法允许你在不修改原始类的情况下&#xff0c;添加新的方法到现有的类型中。 有↓箭头的是扩展方…

vertx idea快速使用

目录 1.官网下载项目 2.修改代码 2.1拷贝代码方式 为了能够快速使用&#xff0c;我另外创建一个新的maven项目&#xff0c;将下载项目的src文件和pom文件拷贝到新建的maven项目。 2.2删除.mvn方式 3.更新配置 4.配置application 5.idea启动项目 1.官网下载项目 从vert…

分布式全文检索引擎ElasticSearch-数据的写入存储底层原理

一、数据写入的核心流程 当向 ES 索引写入数据时&#xff0c;整体流程如下&#xff1a; 1、客户端发送写入请求 客户端向 ES 集群的任意节点&#xff08;称为协调节点&#xff0c;Coordinating Node&#xff09;发送一个写入请求&#xff0c;比如 index&#xff08;插入或更…

android EditText密码自动填充适配

android上的密码&#xff08;其实不仅仅是密码&#xff0c;可以是用户名也可以是邮箱&#xff09;自动填充&#xff0c;是需要考虑适配的。 官方文档&#xff1a;https://developer.android.com/identity/autofill/autofill-optimize?hlzh-cn 什么是自动填充 手机厂商一般会…

【MySQL】非聚簇索引和聚簇索引,索引的创建、查询、删除

目录 存储引擎是MyISAM 非聚簇索引 主键索引&#xff1a; 普通(辅助)索引&#xff1a; 存储引擎是InnoDB 聚簇索引 主键索引&#xff1a; 普通(辅助)索引&#xff1a; 回表查询 创建索引 创建主键索引 主键索引的特点&#xff1a; 创建唯一索引 唯一索引的特点&am…

list的常用操作

list的介绍 list是序列容器&#xff0c;它允许在常数范围O&#xff08;1&#xff09;进行插入和删除在这段序列的任意位置&#xff0c;并且可以双向遍历 它是弥补vector容器的缺点&#xff0c;与vector有互补的韵味&#xff0c; 这里我们可以将其进行与vector进行对比 vect…