acwing算法基础之基础算法--前缀和算法
目录
- 1 知识点
- 2 模板
1 知识点
前缀后下标尽量从1开始,当然不从1开始也是ok的。
a 1 , a 2 , a 3 , . . . , a n a_1,a_2,a_3,...,a_n a1,a2,a3,...,an
S 1 , S 2 , S 3 , . . . S n S_1,S_2,S_3,...S_n S1,S2,S3,...Sn
S i S_i Si:原数组nums中前 i i i个元素的和,注意边界情况 S 0 = 0 S_0=0 S0=0。
前缀和的作用, O ( 1 ) O(1) O(1)时间复杂度下求取原数组中任一区间和[l,r]。
二维前缀和
初始化(类似于递推公式):
S ( i , j ) = S ( i − 1 , j ) + S ( i , j − 1 ) − S ( i − 1 , j − 1 ) + n u m s [ i ] [ j ] S(i,j) = S(i-1,j) + S(i, j-1) - S(i-1,j-1) + nums[i][j] S(i,j)=S(i−1,j)+S(i,j−1)−S(i−1,j−1)+nums[i][j]
计算任一矩形面积:
( x 1 , y 1 ) (x_1,y_1) (x1,y1)、 ( x 2 , y 2 ) (x_2,y_2) (x2,y2)
S ( x 2 , y 2 ) − S ( x 1 − 1 , y 2 ) − S ( x 2 , y 1 − 1 ) + S ( x 1 − 1 , y 1 − 1 ) S(x_2,y_2)-S(x_1-1,y_2)-S(x_2,y_1-1)+S(x_1-1,y_1-1) S(x2,y2)−S(x1−1,y2)−S(x2,y1−1)+S(x1−1,y1−1)
2 模板
//一维前缀和
//原数组nums,它第1个元素是无效的,即nums[0]是无效的
//前缀和数组s
//原数组中[l,r]区间之和为:s[r]-s[l-1]。注意此处的l和r均不考虑无效元素nums[0],也即下标从1开始。
int n = nums.size();
vector<int> s(n);
s[0] = 0;
for (int i = 1; i < n; ++i) {s[i] = s[i-1] + nums[i];
}
//二维前缀和
//原数组nums,其中第0行和第0列是无效值
int n = nums.size(), m = nums[0].size();
vector<vector<int>> s(n, vector<int>(m, 0));
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] + nums[i][j];}
}//(x1,y1) (x2,y2) 注意此处下标从1开始。
//求子矩阵的和
s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1]
相关文章:
acwing算法基础之基础算法--前缀和算法
目录 1 知识点2 模板 1 知识点 前缀后下标尽量从1开始,当然不从1开始也是ok的。 a 1 , a 2 , a 3 , . . . , a n a_1,a_2,a_3,...,a_n a1,a2,a3,...,an S 1 , S 2 , S 3 , . . . S n S_1,S_2,S_3,...S_n S1,S2,S3,...Sn S i S_i Si࿱…...

华为云云耀云服务器L实例评测|Ubuntu 22.04部署edusoho-ct企培版教程 | 支持华为云视频点播对接CDN加速
华为云云耀云服务器L实例评测|Ubuntu 22.04部署edusoho企培版教程 1、选择购买 华为云耀云服务器L实例 简单上云第一步 2、选择你要安装的操作系统,例如 Ubuntu 22.04 server 64bit 3、然后支付订单就行了 4、华为云云耀云服务器L实例创建好之后&#x…...

土木硕设计院在职转码上岸
一、个人介绍 双非土木硕,98年,目前在北京,职位为前端开发工程师,设计院在职期间自学转码上岸🌿 二、背景 本人于19年开始土木研究生生涯,研二期间去地产实习近半年(碧桂园和世茂,这两家的地产…...
js查询月份开始和结束日期
js查询月份开始和结束日期 月份开始和结束 月份开始和结束 整体不是很复杂,使用new Date()方法自带获取最后一天的时间 new Date(a,b,c),传递参数 参数a:是要获取的年份 参数b:是要获取的月份 参数c:是要获取的日期 传递日期为…...
mybatis开发部分核心代码
pom.xml<?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0"xmlns:xsi"http://www.w3.org/2001/XMLSchema-instance"xsi:schemaLocation"http://maven.apache.org/POM/4.0.0 ht…...
Springboot中查看gradle工程使用了哪些仓库
在springboot项目开发中,由于初始化配置文件(init.gradle)可能存在多个目录中(不只一份),可能导致多次重复引入仓库。也有可能配置文件放置位置错误,导致gradle编译时找不到相应的仓库。如果能在编译时查看gradle到底引用了哪些库,…...

c#中的接口
使用IEnumerable统一迭代变量类型 class Program {static void Main(string[] args){int[] nums1 new int[] { 1, 2, 3, 4, 5 };ArrayList nums2 new ArrayList { 1, 2, 3, 4, 5 };Console.WriteLine(Sum(nums1));Console.WriteLine(Sum(nums2));Console.WriteLine(Avg(nums…...
老卫带你学---leetcode刷题(76. 最小覆盖子串)
76. 最小覆盖子串 问题: 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 “” 。 注意: 对于 t 中重复字符,我们寻找的子字符串中该字符数量必…...
Maven-DskipTests和-Dmaven.test.skip=true的区别
DskipTeststrue和-Dmaven.test.skiptrue的区别 1、 -DskipTeststrue 不执行测试用例,但编译测试用例类生成相应的class文件至target/test-classes下,如: mvn clean package -DskipTeststrue2、 -Dmaven.test.skiptrue 完全忽略测试代码的…...
conda中cuda、cuda-toolkit、cuda-nvcc、cuda-runtime的区别
conda中cuda、cuda-toolkit、cuda-nvcc、cuda-runtime的区别 cuda cuda-toolkit cuda-runtime cuda-toolkit 包含 cuda-nvcc CUDA cuda nvidia/label/cuda-11.8.0/linux-64::cuda-11.8.0-0 cuda-cccl nvidia/label/cuda-11.8.0/linux-64::cuda-cccl-11.8.89-0 cuda-comma…...

增强现实抬头显示AR-HUD
增强现实抬头显示(AR-HUD)可以将当前车身状态、障碍物提醒等信息3D投影在前挡风玻璃上,并通过自研的AR-Creator算法,融合实际道路场景进行导航,使驾驶员无需低头即可了解车辆实时行驶状况。结合DMS系统,可以…...

力扣-367.有效的完全平方数
暴力 class Solution { public:bool isPerfectSquare(int num) {for(long i 1; i * i < num; i) {if(i * i num) return true;}return false;} };二分查找 class Solution { public:bool isPerfectSquare(int num) {int left 1, right num;while(left < right) {in…...

小白必看!上位机控制单片机原理
嗨,大家好!今天,我们要探讨一个有趣的话题——"以上位机控制单片机"。不要担心,我们会用最简单的方式来解释这个概念。 首先,你可以把以上位机想象成一台超级聪明的电脑,就像你用来上网、玩游戏、…...
通过套接字手动写一个回显服务器吧
背景:程序员主要编写应用层的代码。真正要发送的数据需要上层协议调用下层协议,而应用层调用传输层时,传输层(系统内核)给应用层提供的一组API统称为Socket API。 系统提供给Java程序员的Socket API主要有两组: 基于UDP的API基于TCP的API目录 一、为什么需要网络编程?——…...
python读取CSV格式文件,遇到的问题20231007
python读取的CSV文件必须是具备相同列数的吗? 在Python中,读取CSV文件时不一定要求每一行都具有相同的列数。CSV文件可以包含不同数量的列,但你需要小心处理不同列数的情况,以确保代码能够正常处理。 通常情况下,CSV文…...
【面试题精讲】为什么重写equals时必须重写hashCode方法?
“ 有的时候博客内容会有变动,首发博客是最新的,其他博客地址可能会未同步,认准https://blog.zysicyj.top ” 首发博客地址[1] 面试题手册[2] 系列文章地址[3] equals() 方法用于比较两个对象是否相等,而 hashCode() 方法用于获取对象的哈希码…...

一文搞懂pytorch hook机制
pytorch的hook机制允许我们在不修改模型class的情况下,去debug backward、查看forward的activations和修改梯度。hook是一个在forward和backward计算时可以被执行的函数。在pytorch中,可以对Tensor和nn.Module添加hook。hook有两种类型,forwa…...
文本挖掘入门
文本挖掘的基础步骤 文本挖掘是从文本数据中提取有用信息的过程,通常包括文本预处理、特征提取和建模等步骤。以下是文本挖掘的基础入门步骤: 数据收集:首先,收集包含文本数据的数据集或文本文档。这可以是任何文本数据ÿ…...
【C++ techniques】Smart Pointers智能指针
Smart Pointers智能指针 看起来、用起来、感觉起来像内置指针,但提供更多的机能。拥有以下各种指针行为的控制权: 构造和析构;复制和赋值;解引。 Smart Pointers的构造、赋值、析构 C的标准程序库提供的auto_ptr template: au…...

LabVIEW利用以太网开发智能液位检测仪
LabVIEW利用以太网开发智能液位检测仪 目前,工业以太网接口在国内外的发展已经达到了相当深入的程度,特别是在自动化控制和工业控制领域有着非常广泛的应用。在工业生产过程中,钢厂的连铸机是前后的连接环节,其中钢水从大钢包进入…...

多模态2025:技术路线“神仙打架”,视频生成冲上云霄
文|魏琳华 编|王一粟 一场大会,聚集了中国多模态大模型的“半壁江山”。 智源大会2025为期两天的论坛中,汇集了学界、创业公司和大厂等三方的热门选手,关于多模态的集中讨论达到了前所未有的热度。其中,…...

docker详细操作--未完待续
docker介绍 docker官网: Docker:加速容器应用程序开发 harbor官网:Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台,用于将应用程序及其依赖项(如库、运行时环…...
【Java学习笔记】Arrays类
Arrays 类 1. 导入包:import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序(自然排序和定制排序)Arrays.binarySearch()通过二分搜索法进行查找(前提:数组是…...
Java如何权衡是使用无序的数组还是有序的数组
在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...
1688商品列表API与其他数据源的对接思路
将1688商品列表API与其他数据源对接时,需结合业务场景设计数据流转链路,重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点: 一、核心对接场景与目标 商品数据同步 场景:将1688商品信息…...

MODBUS TCP转CANopen 技术赋能高效协同作业
在现代工业自动化领域,MODBUS TCP和CANopen两种通讯协议因其稳定性和高效性被广泛应用于各种设备和系统中。而随着科技的不断进步,这两种通讯协议也正在被逐步融合,形成了一种新型的通讯方式——开疆智能MODBUS TCP转CANopen网关KJ-TCPC-CANP…...

学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”
2025年#高考 将在近日拉开帷幕,#AI 监考一度冲上热搜。当AI深度融入高考,#时间同步 不再是辅助功能,而是决定AI监考系统成败的“生命线”。 AI亮相2025高考,40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕,江西、…...

安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖
在Vuzix M400 AR智能眼镜的助力下,卢森堡罗伯特舒曼医院(the Robert Schuman Hospitals, HRS)凭借在无菌制剂生产流程中引入增强现实技术(AR)创新项目,荣获了2024年6月7日由卢森堡医院药剂师协会࿰…...

Python基于历史模拟方法实现投资组合风险管理的VaR与ES模型项目实战
说明:这是一个机器学习实战项目(附带数据代码文档),如需数据代码文档可以直接到文章最后关注获取。 1.项目背景 在金融市场日益复杂和波动加剧的背景下,风险管理成为金融机构和个人投资者关注的核心议题之一。VaR&…...

三分算法与DeepSeek辅助证明是单峰函数
前置 单峰函数有唯一的最大值,最大值左侧的数值严格单调递增,最大值右侧的数值严格单调递减。 单谷函数有唯一的最小值,最小值左侧的数值严格单调递减,最小值右侧的数值严格单调递增。 三分的本质 三分和二分一样都是通过不断缩…...