算法——前缀和算法

1. 什么是前缀和算法

前缀和算法(Prefix Sum)是一种用于快速计算数组元素之和的技术。它通过预先计算数组中每个位置前所有元素的累加和,将这些部分和存储在一个新的数组中,从而在需要计算某个区间的和时,可以通过简单的减法操作得到结果,而不必重新遍历整个区间。

2. 一维前缀和

在这里我们通过一个例题来讲解:【模板】前缀和_牛客题霸_牛客网 (nowcoder.com)

题目描述如下

我们在一个数组中想要q次访问一段下标为 [l, r] 的数据和即

我们稍加分析可以发现,如果我们使用暴力解法(将区间内所有数字相加)时间复杂度为O(q*N),在这里我们可以使用前缀和的算法,来使每次访问的时间复杂度降低到O(1),在这里我们要提前预备好一个dp数组,dp[i]表示从下标1开始到下标i的数值和,dp[i] = dp[i-1] + arr[i],这样填完dp表后,[l, r]的数值和sum = dp[r] - dp[l-1],此外在这里有一个细节需要我们注意:下标为什么是从1开始的?——假如要计算[0, 2]的话,我们需要使用dp[2] - dp[-1],这样就会带来不便。

我们可以得到这道题的代码

#include <iostream>
#include <vector>
using namespace std;int main() 
{int n = 0, q = 0;cin >> n >> q;vector<int> arr(n + 1);for (int i = 1; i <= n; i++) cin >> arr[i];// 使用long long 避免整型溢出vector<long long> dp(n + 1);for (int i = 1; i <= n; i++) dp[i] = dp[i-1] + arr[i];int l = 0, r = 0;while (q--){cin >> l >> r;cout << dp[r] - dp[l-1] << endl;}return 0;
}

3. 二维前缀和

在这里我们使用另一个例题:【模板】二维前缀和_牛客题霸_牛客网 (nowcoder.com)

在这里,我们需要得到从下标(x1, y1)->(x2, y2)所有数值和,我们同样可以使用前缀和来解决。二维的前缀和与一维的相似,我们可以规定dp[i][j]表示从下标(1, 1)->(i, j)所有数值和,我们要计算的dp[i][j]可以按如下方式计算

即dp[i][j] = dp[i-1][j] + dp[i][j-1] + arr[i][j] - dp[i-1][j-1],在预备好了dp数组过后,我们如何来使用它呢?图解如下

我们可以使用如下代码解决此问题

#include <iostream>
#include <vector>
using namespace std;int main() 
{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];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];int x1 = 0, y1 = 0, x2 = 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;
}

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

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

C++ 内存管理(newdelete)

目录 本节目标 1. C/C内存分布 2. C语言中动态内存管理方式&#xff1a;malloc/calloc/realloc/free 3. C内存管理方式 3.1 new/delete操作内置类型 3.2 new和delete操作自定义类型 4. operator new与operator delete函数 5. new和delete的实现原理 6. 定位new表达式(placem…

设置idea中放缩字体大小

由于idea没默认支持ctrl滚轴对字体调节大小&#xff0c;下面一起设置一下吧&#xff01; 点击 文件 -> 设置 按键映射 -> 编辑器操作 -> 搜索栏输入f 点击减小字体大小 -> 选择增加鼠标快捷键 按着ctrl键&#xff0c;鼠标向下滚动后&#xff0c;点击确定即可 然后…

微软.NET6开发的C#特性——类、结构体和联合体

我是荔园微风&#xff0c;作为一名在IT界整整25年的老兵&#xff0c;看到不少初学者在学习编程语言的过程中如此的痛苦&#xff0c;我决定做点什么&#xff0c;下面我就重点讲讲微软.NET6开发人员需要知道的C#特性。 C#经历了多年发展&#xff0c; 进行了多次重大创新&#xf…

Hadoop搭建(完全分布式)

节点分布&#xff1a; bigdata-masterbigdata-slave1bigdata-salve2 NameNode NodeManager NodeManager SecondaryNameNodeDataNodeDataNodeResourceManagerNodeManagerDataNode 目录 一、jdk安装&#xff1a; 二、hadoop安装 一、jdk安装&#xff1a; jdk-8u212链接&am…

git 使用 (备查)

git忽略清单 添加忽略清单 SSH免登录 ssh协议可以实现免登录操作&#xff0c;身份验证通过密钥实现。 跨团队写作 解决冲突 拉取 克隆 拉取最新版本 推送 远程仓库别名 直接使用git push推送 多人协作开发 分支命令 合并分支命令在主分支使用&#xff0c;将develop分支合并到…

【力扣】快乐数,哈希集合 + 快慢指针 + 数学

快乐数原题地址 方法一&#xff1a;哈希集合 定义函数 getNext(n) &#xff0c;返回 n 的所有位的平方和。一直执行 ngetNext(n) &#xff0c;最终只有 2 种可能&#xff1a; n 停留在 1 。无限循环且不为 1 。 证明&#xff1a;情况 1 是存在的&#xff0c;如力扣的示例一…

【C++基础入门】七、指针(定义和使用、所占内存空间、空指针和野指针、const关键字修饰指针、指针和数组、指针和函数)

七、指针 7.1 指针的基本概念 指针的作用&#xff1a; 可以通过指针间接访问内存 内存编号是从0开始记录的&#xff0c;一般用十六进制数字表示可以利用指针变量保存地址 7.2 指针变量的定义和使用 指针变量定义语法&#xff1a; 数据类型 * 变量名&#xff1b; 示例&…

深入Pandas:精通文本数据处理的20+技巧与应用实例【第68篇—python:文本数据处理】

文章目录 Pandas文本数据处理方法详解1. str/object类型转换2. 大小写转换3. 文本对齐4. 获取长度5. 出现次数6. 编码方向7. 字符串切片8. 字符串替换9. 字符串拆分10. 字符串连接11. 字符串匹配12. 去除空格13. 多条件过滤14. 字符串排序15. 字符串格式化16. 多列文本操作17. …

PHPExcel导出excel

PHPExcel下载地址 https://gitee.com/mirrors/phpexcelhttps://github.com/PHPOffice/PHPExcel 下载后目录结构 需要的文件如下图所示 将上面的PHPExcel文件夹和PHPExcel.php复制到你需要的地方 这是一个简单的示例代码 <?php$dir dirname(__FILE__); //require_once …

「Mybatis实战五」:Mybatis核心文件详解 - MyBatis常用配置environments、properties

一、MyBatis核心配置文件层级关系 ​ 本文代码在 Mybatis初体验&#xff1a;一小时从入门到运行你的第一个应用 所构建的基础代码结构之上&#xff0c;进行修改。 MyBatis 的配置文件包含了会深深影响 MyBatis 行为的设置和属性信息。 配置文档的顶层结构如下&#xff1a; 二…

Github 2024-02-08 开源项目日报 Top9

根据Github Trendings的统计&#xff0c;今日(2024-02-08统计)共有9个项目上榜。根据开发语言中项目的数量&#xff0c;汇总情况如下&#xff1a; 开发语言项目数量Ruby项目1HTML项目1Python项目1Scala项目1PLpgSQL项目1Rust项目1NASL项目1C项目1TypeScript项目1非开发语言项目…

vue3:26—新的内置组件

目录 Teleport Suspense Teleport 什么是Teleport? Teleport 是一种能够将我们的组件html结构移动到指定位置的技术 当在元素中的css使用了filter滤镜属性的时候&#xff0c;会导致内部 fixed 元素定位发生错误&#xff0c;即不再相对 viewport 进行定位&#xff0c;而是相对…

Redis篇之redis是单线程

一、redis是单线程 Redis是单线程的&#xff0c;但是为什么还那么快&#xff1f;主要原因有下面3点原因&#xff1a; 1. Redis是纯内存操作&#xff0c;执行速度非常快。 2. 采用单线程&#xff0c;避免不必要的上下文切换可竞争条件&#xff0c;多线程还要考虑线程安全问题。 …

【Google Bard】免费生成图像——功能和使用方法详解

Google Bard 关于Bard 图片生成功能打开Bard通过Bard来生成图片Bard Vs Bing Vs Dall-EBard的生成结果Bing的生成结果Dall-E 的生成结果 总结 关于Bard 图片生成功能 Google在2月1日&#xff08;当地时间&#xff09;宣布&#xff0c;其对话型AI“Bard”新增了图像生成功能。 …

ICLR 2024 | Harvard FairSeg:第一个研究分割算法公平性的大型医疗分割数据集

近年来&#xff0c;人工智能模型的公平性问题受到了越来越多的关注&#xff0c;尤其是在医学领域&#xff0c;因为医学模型的公平性对人们的健康和生命至关重要。高质量的医学公平性数据集对促进公平学习研究非常必要。现有的医学公平性数据集都是针对分类任务的&#xff0c;而…

【Java】ArrayList和LinkedList的区别是什么

目录 1. 数据结构 2. 性能特点 3. 源码分析 4. 代码演示 5. 细节和使用场景 ArrayList 和 LinkedList 分别代表了两类不同的数据结构&#xff1a;动态数组和链表。它们都实现了 Java 的 List 接口&#xff0c;但是有着各自独特的特点和性能表现。 1. 数据结构 ArrayList…

泽攸科技ZEM系列台扫助力环境科研创新:可见光催化抗生素降解的探索

环境污染和能源短缺是当今人类社会面临的最严重威胁之一。为了克服这些问题&#xff0c;特别是在污水处理过程中&#xff0c;寻找新的技术来实现清洁、高效、经济的发展显得尤为重要。在各种工业废水中&#xff0c;抗生素的过量排放引起了广泛关注。抗生素的残留会污染土壤、水…

Openresty+Lua+Redis实现高性能缓存

一、背景 当我们的程序需要提供较高的并发访问时&#xff0c;往往需要在程序中引入缓存技术&#xff0c;通常都是使用Redis作为缓存&#xff0c;但是要再更进一步提升性能的话&#xff0c;就需要尽可能的减少请求的链路长度&#xff0c;比如可以将访问Redis缓存从Tomcat服务器…

部署 Spring 项目到 Linux 云服务器上

关于 Linux 服务器安装 JDK ,Mysql&#xff0c;配置安全组&#xff08;这些都是必要的&#xff09; 推荐看在 Linux 上搭建 Java Web 项目环境&#xff08;最简单的进行搭建&#xff09; 流程 1.上传Jar包到服务器 要想部署 Spring 项目&#xff0c;先要将 Spring 项目打成 J…

【51单片机】实现一个动静态数码管显示项目(超全详解&代码&图示)(5)

前言 大家好吖&#xff0c;欢迎来到 YY 滴单片机 系列 &#xff0c;热烈欢迎&#xff01; 本章主要内容面向接触过单片机的老铁 主要内容含&#xff1a; 欢迎订阅 YY滴C专栏&#xff01;更多干货持续更新&#xff01;以下是传送门&#xff01; YY的《C》专栏YY的《C11》专栏YY…