当前位置: 首页 > news >正文

【前缀和算法】--- 一维和二维前缀和模板

 Welcome to 9ilk's Code World

       

(๑•́ ₃ •̀๑) 个人主页:       9ilk

(๑•́ ₃ •̀๑) 文章专栏:    算法Journey  


本文开始,博主开始讲解有关前缀和的算法,本篇博客我们先来了解一下有关前缀和的两个模板。


🏠 一维前缀和模板

📌 题目内容

一维前缀和

📌题目解析

  • 数组的下标是从1开始的。
  • 数组中每个值的范围是−10^9 ≤ a[i] ≤ 10^9,因此我们需要考虑如果多个值相加用int可能溢出,可以考虑用long long.

📌算法原理

✏️ 思路一:暴力解法

 暴力解法很简单就是进行模拟,每次查询从L下标开始遍历直到到R下标。最坏情况是L是1下标,而R是n下标,n为数组长度。因此时间复杂度为O(q*n).

有没有什么优化的解法?

✏️ 思路二:前缀和

前缀和算tg法分为两步:1.预处理出来一个前缀和数组。2.使用前缀和数组。它可以用来快速求出数组中某一个连续区间的和。

  • 预处理出前缀和数组

假设有一个数组arr,同时有个相关联的数组dp,dp[i]表示的是arr数组[1,i]区间内所有值和。

我们发现,比如dp[3]是【1,3】区间值的和,那么就相当于是【1,2】区间的和+arr[3].

因此我们可以得出公式dp[i] = dp[i-1] + arr[i].

通过公式我们在遍历一遍数组的同时,就可以求出前缀和数组。

  • 使用前缀和数组

题目要我们求出[l,r]区间内值的和,由于我们提前求出了前缀和数组,我们发现所求区间 = 总和 - 前一段区间,因此【l,r】= dp[r] - dp[l-1],这个过程是很快的达到了O(1)

参考代码:

typedef long long ll;
int main() 
{int n = 0;int q = 0; //查询次数cin >> n >> q;vector<ll> v(n+1,0);vector<ll> dp(n+1,0);ll prev = 0;//获得前缀和数组//dp[i]表示的是从1到i区间值的总和for(int i = 1 ; i <= n ; i++){cin >> v[i];dp[i] = dp[i-1] + v[i];} //使用前缀和数组while(q--){int l = 0;int r = 0;cin >> l >> r;cout << dp[r] - dp[l-1] << endl; }return 0;
}
  • 细节问题

我们前缀和数组下标是从1开始的,如果下标从0开始,当求[0,2]区间的值之和时就转化成dp[2] - dp[-1]这个dp[-1]是个边界情况需要我们特殊处理且原本数组没有-1开始的;如果下标从1开始,当求[1,2]区间的值之和时转化成dp[2] - dp[0],对于dp[0]我们就容易将它处理为0即可

总结:前缀和数组下标从1开始,是为了处理边界情况。

🏠 二维前缀和数组

📌 题目内容

二维前缀和

📌 题目解析

  • 本题数据范围仍然过大,用int会有溢出的风险。
  • 题目要我们求的是以(x1,y1)为左上角,(x2,y2)为右下角的子矩阵的和。

📌 算法原理

✏️ 思路一:暴力解法

暴力解法也就是模拟从第一个点开始直接按照划分区域进行遍历,最坏情况是整个矩阵,时间复杂度是O(n*m*q).

✏️ 思路二:二维前缀和

  • 预处理出二维前缀和数组

假设有一个二维数组arr,dp数组是一个与它关联的数组。dp[i][j]表示以(1,1)为左上角,(i,j)为右上角形成的子矩阵中值之和。任取一块区域,假设D为(i,j)点,若我们要求dp[i][j]也就是求(1,1)到(i,j)区域的和,我们可以将这四部分相加,由于B和C不好求,我们可以利用A(dp[i-1][j-1])来间接求这两部分,但是不要忘记减去多进来的A。由于A+B和A+C在dp数组中分别对应的是dp[i-1][j]和dp[i][j-1],因此我们可以得到公式:

dp[ i ][ j ] = dp[ i-1 ][ j ] + dp[ i ][ j-1 ] + arr[ i ][ j ] - dp[ i-1][ j-1 ].

通过公式,我们在遍历二维数组时就可以求出对应的dp二维数组。

  • 使用二维前缀和数组

题目要我们求以(x1,y1)为左上角,(x2,y2)为右上角区域的值之和,也就是求区域D。因此D可以由整体减去A,B,C三部分,由于B和C不好求,所以我们利用A间接求。于是有D=(A+B+C+D) - (A+C) - (A+B) +A。对于A就是dp[x1][y1],A+B就是dp[x1-1][y2],A+C就是dp[x2][y1-1],于是得到公式:D = dp[x2][y2] - dp[x2][y1-1] - dp[x1-1][y2] + dp[x1-1][y1-1]。此时 我们由于提前得到的二维前缀和数组,我们能很快得出D的值,时间复杂度是O(1).

时间复杂度优化为了O(m*n) + O(q).

参考代码:

int main() 
{int n = 0; //行 int m = 0; //列int q = 0; //查询次数cin >> n >> m >> q;vector<vector<long long>> vv(n + 1);vector<vector<long long>> dp(n + 1);for (int i = 0; i <= n; i++){vv[i].resize(m + 1, 0);dp[i].resize(m + 1, 0);if (i >= 1){for (int j = 1; j <= m; j++){cin >> vv[i][j];}}}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] + vv[i][j] - dp[i-1][j-1];}}while (q--){int x1, x2, y1, y2 = 0;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. 一维和二维前缀和数组下标都是从1开始。

2.当我们需要快速求出一段连续区间或区域时,可以考虑用前缀和数组,用前缀和数组间接求我们需要的。

3.我们可以根据场景推导出公式获得前缀和数组。

相关文章:

【前缀和算法】--- 一维和二维前缀和模板

Welcome to 9ilks Code World (๑•́ ₃ •̀๑) 个人主页: 9ilk (๑•́ ₃ •̀๑) 文章专栏&#xff1a; 算法Journey 本文开始,博主开始讲解有关前缀和的算法&#xff0c;本篇博客我们先来了解一下有关前缀和的两个模板。 &#x1f3e0; 一维前缀和模板 &…...

有些信息注定会丢失

智能在分析问题、做出决策时&#xff0c;总是希望获取尽可能多的信息&#xff0c;以此更加准确地决策。然而&#xff0c;很遗憾的是&#xff0c;有一些信息注定会丢失&#xff0c;不可能获取完全的信息&#xff0c;而且即使能够获取&#xff0c;智能也不能完全利用。 这一点与…...

c#中Task.Run 和使用 Task 构造函数创建任务的区别

Task.Run 和使用 Task 构造函数创建任务是两种不同的方法&#xff0c;它们在某些方面有显著的区别&#xff1a; 启动方式: Task.Run 是一个静态方法&#xff0c;它立即启动一个任务并在后台执行指定的工作。它通常用于快速启动一个简单的后台任务。使用 Task 构造函数创建任务&…...

使用nginx做代理转发

需求1&#xff1a;通过监听服务器的80端口&#xff0c;将请求转发到另一台服务器的8070端口 打开nginx/nginx.conf文件 server {listen 80;server_name localhost;location /analys {proxy_pass http://10.xx.xx.xx:8070/;} }需求2&#xff1a;通过监听服务器的80端口&am…...

Java前端与后端交互:JSON与XML数据交换 - 掌握现代Web开发的核心技能

引言 随着互联网技术的不断进步&#xff0c;Web应用变得越来越复杂&#xff0c;从前端到后端的每一个环节都需要精心设计以保证良好的用户体验。在这个过程中&#xff0c;数据的传递扮演着至关重要的角色。无论是简单的表单提交还是复杂的API调用&#xff0c;都需要一种可靠的…...

网络攻击原理及过程

网络攻击原理表 攻击者 内容 攻击访问 攻击效果 攻击意图 黑客 挑战 间谍 用户命令 破坏信息 好奇 恐怖主义者 脚本或程序 本地访问 信息泄密 获取情报 公司职员 自治主体 远程访问 窃取服务 经济利益 职业犯罪分子 电磁泄露 拒绝服务 恐怖事…...

day30(8/16)——ansible

目录 一、回顾 1、mysql和python 1. mysql5.7 2. 可以使用pymysql非交互的管理mysql 2、mycat中间件 1. 独属于mysql主从的负载均衡策略 2.配置写主读从 3. 步骤 3.1 安装jdk 3.2 mycat 3.3 配置 3.4 启动和调试 二、运维自动化&#xff08;ansible&#xff09; 1、任务背…...

fastadmin 安装

环境要求&#xff0c;大家可以参考官方文档的&#xff0c;我这里使用的是phpstudy&#xff0c;很多已经集成了。 注意一点&#xff0c;PHP 版本&#xff1a;PHP 7.4 。 第二步&#xff1a;下载 下载地址&#xff1a;https://www.fastadmin.net/download.html 进入下载地址后…...

Unity动画模块 之 3D模型导入基础设置 Rig页签

​本文仅作笔记学习和分享&#xff0c;不用做任何商业用途本文包括但不限于unity官方手册&#xff0c;unity唐老狮等教程知识&#xff0c;如有不足还请斧正​​ 1.Rig页签 Rig 选项卡 - Unity 手册&#xff0c;rig是设置骨骼与替身系统的&#xff0c;工作流程如下 Avatar是什么…...

⭐️Python在Windows命令行(Command Prompt)运行Python脚本或交互式地执行Python代码详解

Python在Windows命令行&#xff08;Command Prompt&#xff09;运行Python脚本或交互式地执行Python代码详解 Python在Windows命令行&#xff08;Command Prompt&#xff09;运行Python脚本或交互式地执行Python代码详解一、安装Python二、运行Python脚本1. 打开命令行2. 导航到…...

Python | Leetcode Python题解之第355题设计推特

题目&#xff1a; 题解&#xff1a; class Twitter:class Node:def __init__(self):self.followee set()self.tweet list()def __init__(self):self.time 0self.recentMax 10self.tweetTime dict()self.user dict()def postTweet(self, userId: int, tweetId: int) ->…...

D. Beard Graph

https://codeforces.com/problemset/problem/165/D 主要是边转点 后面都是简单的线段树维护 我们维护ok标记,val值&#xff0c;黑&#xff08;1),白&#xff08;0&#xff09; id.okl.ok&r.ok id.vall.valr.val 注意特判如果两个点一样是0,如果dfn[u]1>dfn[v]就不…...

使用预训练的 ONNX 格式的 YOLOv8n 模型进行目标检测,并在图像上绘制检测结果

目录 __init__方法&#xff1a; pre_process方法&#xff1a; run方法&#xff1a; filter_boxes方法&#xff1a; view_img方法&#xff1a; ​​​​​​​__init__方法&#xff1a; 初始化类的实例时&#xff0c;创建一个onnxruntime的推理会话&#xff0c;加载名为yolo…...

mac安装xmind

文章目录 介绍软件功能下载安装1.下载完成后打开downloads 双击进行安装2.将软件拖到应用程序中3.在启动台中搜索打开4.提示损坏问题解决5.执行完成关闭命令窗口6.打开成功&#xff0c;点击继续&#xff0c;跳过登录7.打开成功后&#xff0c;点击关于 小结 介绍 XMind 是一款流…...

MySQL分区表入门

MySQL数据库的分区表是一种将表数据分成逻辑上相关的部分并存储在不同的物理位置的技术。使用分区表可以提高查询性能、简化数据维护和提供更好的数据管理。 以下是MySQL中创建和使用分区表的一般步骤&#xff1a; 设计分区策略&#xff1a; 首先&#xff0c;需要确定如何将表…...

StarRocks 存算分离数据回收原理

前言 StarRocks存算分离表中&#xff0c;垃圾回收是为了删除那些无用的历史版本数据&#xff0c;从而节约存储空间。考虑到对象存储按照存储容量收费&#xff0c;因此&#xff0c;节约存储空间对于降本增效尤为必要。 在系统运行过程中&#xff0c;有以下几种情况可能会需要删…...

【运维】Linux中的xargs指令如何使用?

xargs 是 Linux 中一个非常强大的命令,用于将标准输入中的输出作为参数传递给其他命令。通常情况下,xargs 用于处理长列表或者将多行输入转换成一行。 以下是 xargs 的基本用法和一些常见的例子: 基本语法 command | xargs [options] [command]常见的例子 删除文件:假设…...

日志审计-graylog ssh登录超过6次告警

Apt 设备通过UDP收集日志&#xff0c;在gray创建接收端口192.168.0.187:1514 1、ssh登录失败次数大于5次 ssh日志级别默认为INFO级别&#xff0c;通过系统rsyslog模块处理&#xff0c;日志默认存储在/var/log/auth.log。 将日志转发到graylog vim /etc/rsyslog.conf 文件末…...

4. kafka消息监控客户端工具

KafkaKing官网地址 : https://github.com/Bronya0/Kafka-King github下载地址 : Releases Bronya0/Kafka-King (github.com) (windows、macos、linux版本) 云盘下载地址 : https://pan.baidu.com/s/1dzxTPYBcNjCTSsLuHc1TZw?pwd276i (仅windows版本) 连接kafka 输入本地地址…...

鸿蒙环境和模拟器安装

下载华为开发者工具套件&#xff0c;并解压 https://developer.harmonyos.com/deveco-developer-suite/enabling/kit?currentPage1&pageSize10 双击dmg安装ide 复制并解压sdk 安装模拟器 https://yuque.antfin-inc.com/ainan.lsd/cm586u/po19k1mi9b2728da?singleDoc#…...

使用分级同态加密防御梯度泄漏

抽象 联邦学习 &#xff08;FL&#xff09; 支持跨分布式客户端进行协作模型训练&#xff0c;而无需共享原始数据&#xff0c;这使其成为在互联和自动驾驶汽车 &#xff08;CAV&#xff09; 等领域保护隐私的机器学习的一种很有前途的方法。然而&#xff0c;最近的研究表明&…...

【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例

文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...

对WWDC 2025 Keynote 内容的预测

借助我们以往对苹果公司发展路径的深入研究经验&#xff0c;以及大语言模型的分析能力&#xff0c;我们系统梳理了多年来苹果 WWDC 主题演讲的规律。在 WWDC 2025 即将揭幕之际&#xff0c;我们让 ChatGPT 对今年的 Keynote 内容进行了一个初步预测&#xff0c;聊作存档。等到明…...

三体问题详解

从物理学角度&#xff0c;三体问题之所以不稳定&#xff0c;是因为三个天体在万有引力作用下相互作用&#xff0c;形成一个非线性耦合系统。我们可以从牛顿经典力学出发&#xff0c;列出具体的运动方程&#xff0c;并说明为何这个系统本质上是混沌的&#xff0c;无法得到一般解…...

EtherNet/IP转DeviceNet协议网关详解

一&#xff0c;设备主要功能 疆鸿智能JH-DVN-EIP本产品是自主研发的一款EtherNet/IP从站功能的通讯网关。该产品主要功能是连接DeviceNet总线和EtherNet/IP网络&#xff0c;本网关连接到EtherNet/IP总线中做为从站使用&#xff0c;连接到DeviceNet总线中做为从站使用。 在自动…...

鱼香ros docker配置镜像报错:https://registry-1.docker.io/v2/

使用鱼香ros一件安装docker时的https://registry-1.docker.io/v2/问题 一键安装指令 wget http://fishros.com/install -O fishros && . fishros出现问题&#xff1a;docker pull 失败 网络不同&#xff0c;需要使用镜像源 按照如下步骤操作 sudo vi /etc/docker/dae…...

Mac下Android Studio扫描根目录卡死问题记录

环境信息 操作系统: macOS 15.5 (Apple M2芯片)Android Studio版本: Meerkat Feature Drop | 2024.3.2 Patch 1 (Build #AI-243.26053.27.2432.13536105, 2025年5月22日构建) 问题现象 在项目开发过程中&#xff0c;提示一个依赖外部头文件的cpp源文件需要同步&#xff0c;点…...

Spring是如何解决Bean的循环依赖:三级缓存机制

1、什么是 Bean 的循环依赖 在 Spring框架中,Bean 的循环依赖是指多个 Bean 之间‌互相持有对方引用‌,形成闭环依赖关系的现象。 多个 Bean 的依赖关系构成环形链路,例如: 双向依赖:Bean A 依赖 Bean B,同时 Bean B 也依赖 Bean A(A↔B)。链条循环: Bean A → Bean…...

Python 实现 Web 静态服务器(HTTP 协议)

目录 一、在本地启动 HTTP 服务器1. Windows 下安装 node.js1&#xff09;下载安装包2&#xff09;配置环境变量3&#xff09;安装镜像4&#xff09;node.js 的常用命令 2. 安装 http-server 服务3. 使用 http-server 开启服务1&#xff09;使用 http-server2&#xff09;详解 …...

论文阅读笔记——Muffin: Testing Deep Learning Libraries via Neural Architecture Fuzzing

Muffin 论文 现有方法 CRADLE 和 LEMON&#xff0c;依赖模型推理阶段输出进行差分测试&#xff0c;但在训练阶段是不可行的&#xff0c;因为训练阶段直到最后才有固定输出&#xff0c;中间过程是不断变化的。API 库覆盖低&#xff0c;因为各个 API 都是在各种具体场景下使用。…...