【算法】手把手学会前缀和

这篇具有很好参考价值的文章主要介绍了【算法】手把手学会前缀和。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

前缀和

前缀和的好处

公式的推导

例题:前缀和

二维前缀和

推导公式

 例题: 子矩阵的和


前缀和

前缀和的好处

🎵前缀和算法可以理解为是一种以空间换时间的方式,通过建立一个新的数组来存储从头到当前位置的数据的总和

公式的推导

初始化数组

 🎵前缀和数组的初始化就是将前 个数存在一个新的数组之中,这里用 表示原数组,表示前缀和数组。在计算时,由于当前 i 位置的上一位表示的就是1 ~ i-1的前缀和,于是我们便可以在此基础上加上原数组上的值(a[i])就是当前位置的前缀和了。

🎵于是初始化的公式便优化成s[i] = s[i-1] + a[i]

🎵也正是这个原因前缀和数组的下标必须从1开始,且默认s[0] = 0 才能保证s[1]就是a[1]的本身。如此循环一趟便可完成前缀和数组的初始化。

前缀和算法,算法,算法,numpy,数据结构

前缀和算法,算法,算法,numpy,数据结构

区间和

🎵求区间和才是特意建立前缀和数组的目的,要求区间和的时候若我们每次都暴力地直接进行区间遍历,随着区间长度和计算次数的增加,会出现非常多次的重复计算。

🎵若提前用前缀和数组记录下来就可以将每次计算的时间复杂度优化到 O(1) ,极大地优化了代码的效率。那前缀和数组怎么求区间和呢,让我们现在来看看。

 🎵我们设左边界为 ,右边界为 ,根据性质便可以得到如下等式,若要求数组的一段区间和,只需要在前缀和数组中用 的值减去 l-1 的值,此行为即表示将左边界之前的值删去,那剩下的便是我们要求的区间和了。

前缀和算法,算法,算法,numpy,数据结构

前缀和算法,算法,算法,numpy,数据结构

例题:前缀和

🎵 传送门:AcWing 795. 前缀和

前缀和算法,算法,算法,numpy,数据结构

🎵题目要求使用前缀和数组进行区间数的求和,就跟我们上面推导的公式一样,只需要初始化完前缀和数组后,根据公式输出结果就能够完成题目要求。更多细节我们通过代码来看看。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

const int N = 100010;
int n,m;
int s[N],a[N];

int main() 
{
	scanf("%d%d",&n,&m);
	for(int i = 1;i<=n;i++)
	{
		scanf("%d",&a[i]);     //读入原数组
		s[i] = s[i-1] + a[i];  //初始化前缀和数组
	}
	while(m--)  //  m组数据
	{
		int l,r;
		scanf("%d%d",&l,&r);
		printf("%d\n",s[r]-s[l-1]);  //根据边界求区间和
	}
	return 0;
}

二维前缀和

🎵二维前缀和便是在一维前缀和的基础上,拓展了一个维度,在(i, j)位置表达的便是从(1,1)开始一直到(i, j)这个范围内所有的值的和。注意: 这里画的图都是以(1,1)为起点进行表示的。

前缀和算法,算法,算法,numpy,数据结构

推导公式

初始化

🎵这里从图示出发,我们也很容易观察到,若我们想要对其进行初始化只需要,用上部分矩阵加上左部分矩阵,但这个过程中中间部分被算了两次所以需要扣掉一次,最后再补上当前位置的值即可,即s[i,j] = a[i, j] + s[i, j-1] + s[i-1, j] - s[i-1, j-1]

前缀和算法,算法,算法,numpy,数据结构

求区间和

🎵假设求的是 (x1,y1) 到 (x2,y2) 的区间和,我们可以看到目标区间就是紫色的矩阵,就像求一维前缀和那样,我们只要保留目标区间,其他多余的部分都要删除,现在我们要删除掉的就是目标矩阵上方左边的两个矩阵,即 s[x1-1, y2] 和 s[x2, y1-1] ,很明显两者有一个重复的空间s[x1-1, y1-1](数据再大一点就不仅仅只是一格而已),而连续扣掉两个矩阵后这个重复的空间便会被减去两遍,于是我们需要将其加一遍回来。

🎵即 s[x1y1,x2y2] = s[x2, y2] - s[x2, y1-1] - s[x1-1, y2] + s[x1-1, y1-1]

前缀和算法,算法,算法,numpy,数据结构

 例题: 子矩阵的和

🎵 传送门: AcWing 796. 子矩阵的和

前缀和算法,算法,算法,numpy,数据结构

🎵 通过上面的讲解,这道题目就变得相当简单了,根据题目要求建立二维前缀和数组,之后根据公式求区间和,便可完成任务要求。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

const int N = 1010;
int a[N][N], s[N][N];
int n, m, q;

int main()
{
	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]);     //原数组输入
		}
	}

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];  //初始化二维前缀和数组
		}
	}
	while (q--)
	{
		int x1, y1, x2, y2;
		scanf("%d%d%d%d", &x1, &y1, &x2, &y2);  //接收区间
		printf("%d\n", s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1]); //根据区间和的公式求区间和
	}
	return 0;
}

🎵 好了这次前缀和数组的入门讲解到这里就结束了,如果对你有用的话还请留下你的三连加关注。关注博主,共同进步!!!文章来源地址https://www.toymoban.com/news/detail-797564.html

到了这里,关于【算法】手把手学会前缀和的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Linux、CentOS超详细修改ip方法,手把手步骤教学,小白也能学会

    目录 1.切换root用户   1.1输入命令   1.2输入密码   1.2成功登录   1.3登录失败 2.使用root修改配置文件   2.1输入命令   2.2进入编辑模式    2.2.1修改BOOTPROTO    2.2.2修改ONBOOT    2.2.3修改ip和掩码等    2.2.4结果  2.3退出保存  2.4查看修改是否成功 ​3.重启网络服务 4.查看ip是否

    2024年02月07日
    浏览(60)
  • 数据结构->手把手教入门栈与列队(基础)

    ✅作者简介:大家好,我是橘橙黄又青,一个想要与大家共同进步的男人😉😉 🍎个人主页:橘橙黄又青-CSDN博客 栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除 操作的一端称为栈顶,另一端称为栈底。栈中的数据元素遵守 后

    2024年03月24日
    浏览(205)
  • 手把手教你学会接口自动化系列十一-将用例写在json中,持久化管理起来下

    上一篇我写了登录,我们发现json还是没有什么大问题,还蛮好用的,但是我们再写下一个,比如线索新建接口的时候,我们写着写着会发现问题: 我们写获取url的没有问题,代码如下: # 读取JSON文件 url = baseUrl[\\\'host\\\']+read_json_file(jsonpath)[\\\'url\\\'] print(url) 下一个我们要获取的是

    2024年01月18日
    浏览(46)
  • 【数据结构】—堆详解(手把手带你用C语言实现)

                                            食用指南:本文在有C基础的情况下食用更佳                                          🔥 这就不得不推荐此专栏了: C语言                                        ♈️ 今日夜电波: 水星—今泉愛夏              

    2024年02月07日
    浏览(59)
  • 【初识数据结构】手把手教会你时间复杂度的计算方法

    前言   大家好啊,这里是幸麟 一名普通的大学牲 🧩希望可以不断的进步,因此也一直在学习 如果有写的不好或者写错的地方 欢迎在评论区指正 前言后的小前言 不知道在大家学习算法时有没有遇到这样一种情况,在看大佬题解或者讲解视频时 总能找到一个叫 时间复杂度

    2024年02月09日
    浏览(79)
  • 数据结构->顺序表实战指南,(手把手教会你拿捏数据结构顺序表)

    文章目录 ✅作者简介:大家好,我是橘橙黄又青,一个想要与大家共同进步的男人😉😉 🍎个人主页:橘橙黄又青-CSDN博客 今天开始我们正式进入数据结构的学习了,这篇简单了解一下: 线性表的存储结构:顺序存储结构、链式存储结构; 顺序表的定义:用一段物理地址连

    2024年01月25日
    浏览(61)
  • 速学数据结构 | 手把手教你会单链表的构建方式

    🎬 鸽芷咕 :个人主页  🔥 个人专栏 : 《初阶数据结构》《C语言进阶篇》 ⛺️生活的理想,就是为了理想的生活!    🌈 hello! 各位宝子们大家好啊!今天给大家带来的是初阶数据结构中单链表的构建方式,手把手教会你单链表 !    ⛳️ 链表是指一种逻辑上是连在一

    2024年02月08日
    浏览(86)
  • vue2使用axios封装请求数据,教会你封装,简单易懂,轻松学会axios封装请求数据 看一眼就会 手把手教会

    2、完成上面的步骤还不够,还需要再创建一个文件夹api,然后在文件夹里面创建自定义的文件名(我创建的是cartApi.js)文件名根据自己的需求命名 下面就是根据自己的请求接口以及数据参数请求,下面的请求是一些常见的post、get请求以及传参啥的(仅供参考,可以参考下面

    2024年01月24日
    浏览(53)
  • 手把手教学RRT*(RRTSTAR)三维算法MATLAB仿真(代码可直接运行,视频手把手教学)

            在我以前的作品里有关于RRT算法的视频和代码,今天主要讲解一下RRT*算法的原理。RRT*算法主要是在RRT算法的基础上加上了重写父节点和随机重连的两个步骤。具体的实现方式我想以视频的方式向大家讲解,个人感觉讲解的十分详细。视频连接在这里,希望大家看

    2024年04月17日
    浏览(46)
  • 【图解数据结构】顺序表实战指南:手把手教你详细实现(超详细解析)

    🌈个人主页: 聆风吟 🔥系列专栏: 图解数据结构、算法模板 🔖少年有梦不应止于心动,更要付诸行动。 线性表(linear list):线性表是一种数据结构,由n个具有相同数据类型的元素构成一个有限序列。 线性表可以用数组、链表、栈等方式实现,常见的线性表有数组、链

    2024年01月22日
    浏览(59)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包