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

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(i1,j)+S(i,j1)S(i1,j1)+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(x11,y2)S(x2,y11)+S(x11,y11)

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开始&#xff0c;当然不从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​&#xff1…...

华为云云耀云服务器L实例评测|Ubuntu 22.04部署edusoho-ct企培版教程 | 支持华为云视频点播对接CDN加速

华为云云耀云服务器L实例评测&#xff5c;Ubuntu 22.04部署edusoho企培版教程 1、选择购买 华为云耀云服务器L实例 简单上云第一步 2、选择你要安装的操作系统&#xff0c;例如 Ubuntu 22.04 server 64bit 3、然后支付订单就行了 4、华为云云耀云服务器L实例创建好之后&#x…...

土木硕设计院在职转码上岸

一、个人介绍 双非土木硕&#xff0c;98年&#xff0c;目前在北京&#xff0c;职位为前端开发工程师&#xff0c;设计院在职期间自学转码上岸&#x1f33f; 二、背景 本人于19年开始土木研究生生涯&#xff0c;研二期间去地产实习近半年(碧桂园和世茂&#xff0c;这两家的地产…...

js查询月份开始和结束日期

js查询月份开始和结束日期 月份开始和结束 月份开始和结束 整体不是很复杂&#xff0c;使用new Date()方法自带获取最后一天的时间 new Date(a,b,c),传递参数 参数a&#xff1a;是要获取的年份 参数b&#xff1a;是要获取的月份 参数c&#xff1a;是要获取的日期 传递日期为…...

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项目开发中&#xff0c;由于初始化配置文件(init.gradle)可能存在多个目录中(不只一份)&#xff0c;可能导致多次重复引入仓库。也有可能配置文件放置位置错误&#xff0c;导致gradle编译时找不到相应的仓库。如果能在编译时查看gradle到底引用了哪些库&#xff0c…...

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. 最小覆盖子串 问题&#xff1a; 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串&#xff0c;则返回空字符串 “” 。 注意&#xff1a; 对于 t 中重复字符&#xff0c;我们寻找的子字符串中该字符数量必…...

Maven-DskipTests和-Dmaven.test.skip=true的区别

DskipTeststrue和-Dmaven.test.skiptrue的区别 1、 -DskipTeststrue 不执行测试用例&#xff0c;但编译测试用例类生成相应的class文件至target/test-classes下&#xff0c;如&#xff1a; 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

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

力扣-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…...

小白必看!上位机控制单片机原理

嗨&#xff0c;大家好&#xff01;今天&#xff0c;我们要探讨一个有趣的话题——"以上位机控制单片机"。不要担心&#xff0c;我们会用最简单的方式来解释这个概念。 首先&#xff0c;你可以把以上位机想象成一台超级聪明的电脑&#xff0c;就像你用来上网、玩游戏、…...

通过套接字手动写一个回显服务器吧

背景:程序员主要编写应用层的代码。真正要发送的数据需要上层协议调用下层协议,而应用层调用传输层时,传输层(系统内核)给应用层提供的一组API统称为Socket API。 系统提供给Java程序员的Socket API主要有两组: 基于UDP的API基于TCP的API目录 一、为什么需要网络编程?——…...

python读取CSV格式文件,遇到的问题20231007

python读取的CSV文件必须是具备相同列数的吗&#xff1f; 在Python中&#xff0c;读取CSV文件时不一定要求每一行都具有相同的列数。CSV文件可以包含不同数量的列&#xff0c;但你需要小心处理不同列数的情况&#xff0c;以确保代码能够正常处理。 通常情况下&#xff0c;CSV文…...

【面试题精讲】为什么重写equals时必须重写hashCode方法?

“ 有的时候博客内容会有变动&#xff0c;首发博客是最新的&#xff0c;其他博客地址可能会未同步,认准https://blog.zysicyj.top ” 首发博客地址[1] 面试题手册[2] 系列文章地址[3] equals() 方法用于比较两个对象是否相等&#xff0c;而 hashCode() 方法用于获取对象的哈希码…...

一文搞懂pytorch hook机制

pytorch的hook机制允许我们在不修改模型class的情况下&#xff0c;去debug backward、查看forward的activations和修改梯度。hook是一个在forward和backward计算时可以被执行的函数。在pytorch中&#xff0c;可以对Tensor和nn.Module添加hook。hook有两种类型&#xff0c;forwa…...

文本挖掘入门

文本挖掘的基础步骤 文本挖掘是从文本数据中提取有用信息的过程&#xff0c;通常包括文本预处理、特征提取和建模等步骤。以下是文本挖掘的基础入门步骤&#xff1a; 数据收集&#xff1a;首先&#xff0c;收集包含文本数据的数据集或文本文档。这可以是任何文本数据&#xff…...

【C++ techniques】Smart Pointers智能指针

Smart Pointers智能指针 看起来、用起来、感觉起来像内置指针&#xff0c;但提供更多的机能。拥有以下各种指针行为的控制权&#xff1a; 构造和析构&#xff1b;复制和赋值&#xff1b;解引。 Smart Pointers的构造、赋值、析构 C的标准程序库提供的auto_ptr template: au…...

LabVIEW利用以太网开发智能液位检测仪

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

多模态2025:技术路线“神仙打架”,视频生成冲上云霄

文&#xff5c;魏琳华 编&#xff5c;王一粟 一场大会&#xff0c;聚集了中国多模态大模型的“半壁江山”。 智源大会2025为期两天的论坛中&#xff0c;汇集了学界、创业公司和大厂等三方的热门选手&#xff0c;关于多模态的集中讨论达到了前所未有的热度。其中&#xff0c;…...

docker详细操作--未完待续

docker介绍 docker官网: Docker&#xff1a;加速容器应用程序开发 harbor官网&#xff1a;Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台&#xff0c;用于将应用程序及其依赖项&#xff08;如库、运行时环…...

【Java学习笔记】Arrays类

Arrays 类 1. 导入包&#xff1a;import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序&#xff08;自然排序和定制排序&#xff09;Arrays.binarySearch()通过二分搜索法进行查找&#xff08;前提&#xff1a;数组是…...

Java如何权衡是使用无序的数组还是有序的数组

在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...

1688商品列表API与其他数据源的对接思路

将1688商品列表API与其他数据源对接时&#xff0c;需结合业务场景设计数据流转链路&#xff0c;重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点&#xff1a; 一、核心对接场景与目标 商品数据同步 场景&#xff1a;将1688商品信息…...

MODBUS TCP转CANopen 技术赋能高效协同作业

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

学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”

2025年#高考 将在近日拉开帷幕&#xff0c;#AI 监考一度冲上热搜。当AI深度融入高考&#xff0c;#时间同步 不再是辅助功能&#xff0c;而是决定AI监考系统成败的“生命线”。 AI亮相2025高考&#xff0c;40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕&#xff0c;江西、…...

安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖

在Vuzix M400 AR智能眼镜的助力下&#xff0c;卢森堡罗伯特舒曼医院&#xff08;the Robert Schuman Hospitals, HRS&#xff09;凭借在无菌制剂生产流程中引入增强现实技术&#xff08;AR&#xff09;创新项目&#xff0c;荣获了2024年6月7日由卢森堡医院药剂师协会&#xff0…...

Python基于历史模拟方法实现投资组合风险管理的VaR与ES模型项目实战

说明&#xff1a;这是一个机器学习实战项目&#xff08;附带数据代码文档&#xff09;&#xff0c;如需数据代码文档可以直接到文章最后关注获取。 1.项目背景 在金融市场日益复杂和波动加剧的背景下&#xff0c;风险管理成为金融机构和个人投资者关注的核心议题之一。VaR&…...

三分算法与DeepSeek辅助证明是单峰函数

前置 单峰函数有唯一的最大值&#xff0c;最大值左侧的数值严格单调递增&#xff0c;最大值右侧的数值严格单调递减。 单谷函数有唯一的最小值&#xff0c;最小值左侧的数值严格单调递减&#xff0c;最小值右侧的数值严格单调递增。 三分的本质 三分和二分一样都是通过不断缩…...