前缀和(包括一维和二维)

前缀和

什么是前缀和?用在哪里?有什么好处?

前缀和是在反复求一个序列中不同区间处的元素之和。

例如有以下一个数组:1,2,3,4,5

我们要求a[2]~a[4](不包括a[2])的元素之和,需要写一个循环。

for (int i = x; i <= y; i++) {sum += a[i];
}

但是这样的算法时间复杂度很高,高达O(n^2),当数据规模大时,会超时。

而前缀和可以完美解决这个问题。

for (int i = 1; i <= n; i++) {sum[i] = sum[i - 1] + a[i]
}
cout << sum[y] - sum[x] << endl;

sum[i]就是a[0]+a[1]+...+a[i],在此样例中,sum = [1, 3, 6, 10, 15]

当我们求a[2]~a[4]的和时,就可以输出sum[4] - sum[2]。

一维前缀和

题目描述

输入长度为 n 的数组 A ,求数组 A 中所有长度为 m 的区间里,区间和最大的那个区间的区间和。(数组中可能出现负数)

输入格式

第一行两个整数 n 和 m
第二行给出 n 个整数,第i个整数代表Ai
1<=n<=10^5,1<=m<=n,-10000<=Ai<=10000

输出格式

输出一行答案,最大的区间长度为 m 的区间和

#include <bits/stdc++.h>
using namespace std;int main() {int n, m;cin >> n >> m;int a[100005], s[100005];s[0] = 0;for (int i = 1; i <= n; i++) {cin >> a[i];s[i] = s[i - 1] + a[i];}int mx = 0x80000000;for (int i = m; i <= n; i++) {mx = max(mx, s[i] - s[i - m]);}cout << mx << endl;return  0;
}

二维前缀和

题目描述

小 Q 买下了一片农场,并在其中种下了 n 行 m 列玉米。每株玉米的产量各不相同,减掉成本之后有盈有亏。具体而言,第 i 行第 j 列的玉米的收益为 ai,j,若 ai,j<0 则意味着这株玉米亏本了。现在小 Q 想知道玉米地的收益如何。小 Q 给了你 q 组询问,每组询问都给出四个数 x1, y1, x2, y2,需要你求出行从 x1 到 x2、列从 y1 到 y2 这个矩形区域内玉米的收益之和。

输入格式

第一行输入三个正整数 n,m,q。接下来 n 行,每行 m 个整数,分别表示每一株玉米的收益。接下来 q 行,每行 4 个整数 x1, y1, x2, y2,含义如上。

输出格式

输出 q 行,每行一个数,表示所询问的矩形区域内的玉米收益之和。

sum[x][y] = (1, 1)(x, y)矩阵中的元素和。

sum[x][y] = sum[x - 1][y] + sum[x][y - 1] - sum[x - 1][y - 1]

求x1, y1~x2, y1的公式为:

sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][x2 - 1]

#include <bits/stdc++.h>
using namespace std;int n, m, q, a[3003][3003], s[3003][3003];int main() {memset(s, 0, sizeof (s));cin >> n >> m >> q;for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {cin >> a[i][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;cin >> _x1 >> _y1 >> _x2 >> _y2;cout << s[_x2][_y2] - s[_x1 - 1][_y2] - s[_x2][_y1 - 1] + s[_x1 - 1][_y1 - 1]<< endl;}return 0;
}

学习完前缀和建议去学差分,我的主页里会有。

如果有不当之处,请指出。 

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

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

相关文章

css边框修饰

一、设置线条样式 通过 border-style 属性设置&#xff0c;可选择的一些属性如下&#xff1a; dotted&#xff1a;点线 dashed&#xff1a;虚线 solid&#xff1a;实线 double&#xff1a;双实线 效果如下&#xff1a; 二、设置边框线宽度 ① 通过 border-width 整体设置…

从碎片到整合:EasyCVR平台如何重塑城市感知系统的视频数据生态

随着城市化进程的加速&#xff0c;城市感知系统作为智慧城市的重要组成部分&#xff0c;正逐步成为提升城市管理效率、保障公共安全、优化资源配置的关键手段。EasyCVR视频汇聚融合平台&#xff0c;凭借其强大的数据整合、智能分析与远程监控能力&#xff0c;在城市感知系统中扮…

使用 PowerShell 命令更改 RDP 远程桌面端口(无需修改防火墙设置)

节选自原文&#xff1a;Windows远程桌面一站式指南 | BOBO Blog 原文目录 什么是RDP&#xfffc;开启远程桌面 检查系统版本启用远程桌面连接Windows 在Windows电脑上在MAC电脑上在Android或iOS移动设备上主机名连接 自定义电脑名通过主机名远程桌面使用Hosts文件自定义远程主…

依赖注入之set注入

set注入 set注入&#xff0c;基于set王法实现的&#xff0c;底层通过反射机制调用属性对应的set方法&#xff0c;然后给属性赋值&#xff0c;这种方法要求属性必须对外提供set方法 1. 想让Spring调用对应的set方法&#xff0c;需要配置property标签 2. name属性怎么指定值:s…

云计算Openstack

OpenStack是一个开源的云计算管理平台项目&#xff0c;由美国国家航空航天局&#xff08;NASA&#xff09;和Rackspace公司合作研发并发起&#xff0c;以Apache许可证授权。该项目旨在为公共及私有云的建设与管理提供软件支持&#xff0c;通过一系列相互协作的组件实现云计算服…

python和pyqt-tools安装位置

一.python的安装位置 1.查询安装的python的位置 先查询python&#xff0c;然后输入import sys和sys.path 二.python-tools的安装位置 找到python的文件后按下图路径即可查到tools的文件

利士策分享,攀登职场高峰:成功者的十大特质

利士策分享&#xff0c;攀登职场高峰&#xff1a;成功者的十大特质 在职场这个竞争激烈的舞台上&#xff0c;那些能够迅速崛起、实现职业辉煌的佼佼者&#xff0c;往往凭借一系列独特且鲜明的特质脱颖而出。以下是对这些特质的深入探讨&#xff1a; 第一章&#xff1a;高情商的…

AI芯片WT2605C赋能厨房家电,在线对话操控,引领智能烹饪新体验:尽享高效便捷生活

在智能家居的蓬勃发展中&#xff0c;智能厨电作为连接科技与生活的桥梁&#xff0c;正逐步渗透到每一个现代家庭的厨房中。蒸烤箱作为智能厨电的代表&#xff0c;以其丰富的功能和高效的性能&#xff0c;满足了人们对美食的多样化追求。然而&#xff0c;面对众多复杂的操作功能…

【CSS】字体文本

color 颜色font-size 大小font-family 字体font-style 样式font-weight 加粗text-decoration 下划线text-shadow 阴影text-transform 大小写变换text-indent 缩进text-align 水平对齐 、vertical-align垂直对齐text-overflow 溢出word-wrap 换行word-break 截断white-space 空白…

How to install JetBrains ToolBox in Ubuntu 22.04 LTS?

JetBrains Toolbox 的安装教程 在 2024 年 9 月 28 日&#xff0c;我想和大家分享一下 JetBrains Toolbox 的安装步骤&#xff0c;让你轻松开启高效的开发之旅。 一、准备工作 首先&#xff0c;确保你已经准备好了要安装的 JetBrains Toolbox 文件&#xff0c;可以从官方网站…

(undone) MIT6.824 Lecture1 笔记

参考1MIT课程视频&#xff1a;https://www.bilibili.com/video/BV16f4y1z7kn/?spm_id_from333.337.search-card.all.click&vd_source7a1a0bc74158c6993c7355c5490fc600 参考2某大佬笔记&#xff1a;https://ashiamd.github.io/docsify-notes/#/study/%E5%88%86%E5%B8%83%…

计算机网络详解:发展史、TCP/IP协议、网络通信与应用开发全流程

文章目录 1. 计算机网络的发展史1.1 初期阶段&#xff1a;网络的萌芽&#xff08;1960年代&#xff09;1.2 第二阶段&#xff1a;TCP/IP协议的引入&#xff08;1970-1980年代&#xff09;1.3 第三阶段&#xff1a;互联网的普及与商业化&#xff08;1990年代&#xff09;1.4 现代…

[数据集][目标检测]猪数据集VOC-2856张

数据集格式&#xff1a;Pascal VOC格式(不包含分割的txt文件&#xff0c;仅仅包含jpg图片和对应的xml) 图片数量(jpg文件个数)&#xff1a;2856 标注数量(xml文件个数)&#xff1a;2856 标注类别数&#xff1a;1 标注类别名称:["pig"] 每个类别标注的框数&#xff1a…

The 2024 CCPC Online Contest (C I J三题思路)

写在前面 因为学弟已经问了几个题了&#xff0c;于是乎这场没有vp&#xff0c;准备直接开写了 题目 C. 种树&#xff08;树形dp&#xff09; 题解 只有两种情况&#xff0c; 一种是1-2-3&#xff0c;1是2的父亲&#xff0c;2是3的父亲 另一种是1-2-3&#xff0c;2同时是1…

Meta AI 发布 Llama 3.2

Llama 3.2新闻 Meta公司在其Connect大会上宣布了Llama 3.2的发布&#xff0c;这是其首款能够理解图像和文本的旗舰视觉模型。Llama 3.2包含中型和小型两个版本&#xff08;分别拥有11B与90B参数&#xff09;&#xff0c;以及更轻量化的纯文本模型&#xff08;分别拥有1B与3B参数…

基于 RealSense D435相机实现手部姿态检测

基于 RealSense D435i相机进行手部姿态检测&#xff0c;其中采用 Mediapipe 进行手部检测&#xff0c;以下是详细步骤&#xff1a; Mediapipe 是一个由 Google开发的开源框架&#xff0c;专门用于构建多媒体处理管道&#xff0c;特别是计算机视觉和机器学习任务。它提供了一系列…

并查集 (Union-Find) :从基础到优化

并查集 (Union-Find) 并查集是一种树形数据结构&#xff0c;主要用于处理不相交集合&#xff08;Disjoint Set&#xff09;的合并和查询问题。它特别适用于解决有关连通性的问题&#xff0c;比如在图论中判断两点是否在同一个连通分量中。并查集可以高效地支持以下两种操作&am…

C++--C++11(下)

目录 7.5 完美转发 8 新的类功能 9 可变参数模板 10 lambda表达式 11 包装器 7.5 完美转发 模板中的 && 万能引用 void Fun(int &x){ cout << "左值引用" << endl; } void Fun(const int &x){ cout << "const 左值引用…

java开发jmeter采样器

目录 1.前言 2.新建一个springboot工程 2.1 引入相关依赖 2.2 编写核心代码 2.2.1 取样器代码 2.2.2 取样器界面 2.2.3 sdk接口封装 3.源码打包 3.1 将sdk源码和采样器源码打成jar包 3.2 拷贝引用包 4.配置jmeter脚本 4.1 选择自定义采样器 4.2 界面里面配置参数 1.…

小柴冲刺软考中级嵌入式系统设计师系列二、嵌入式系统硬件基础知识(3)嵌入式系统的存储体系

目录 感悟 一、存储系统的层次结构 存储器系统 二、内存管理单元 三、RAM和ROM的种类与选型 1、RAM RAM分类 2、ROM ROM分类 四、高速缓存Cache 五、其他存储设备 flechazohttps://www.zhihu.com/people/jiu_sheng 小柴冲刺软考中级嵌入式系统设计师系列总目录https…