当前位置: 首页 > 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;其中钢水从大钢包进入…...

基于算法竞赛的c++编程(28)结构体的进阶应用

结构体的嵌套与复杂数据组织 在C中&#xff0c;结构体可以嵌套使用&#xff0c;形成更复杂的数据结构。例如&#xff0c;可以通过嵌套结构体描述多层级数据关系&#xff1a; struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...

(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)

题目&#xff1a;3442. 奇偶频次间的最大差值 I 思路 &#xff1a;哈希&#xff0c;时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况&#xff0c;哈希表这里用数组即可实现。 C版本&#xff1a; class Solution { public:int maxDifference(string s) {int a[26]…...

家政维修平台实战20:权限设计

目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系&#xff0c;主要是分成几个表&#xff0c;用户表我们是记录用户的基础信息&#xff0c;包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题&#xff0c;不同的角色&#xf…...

Spring Boot面试题精选汇总

&#x1f91f;致敬读者 &#x1f7e9;感谢阅读&#x1f7e6;笑口常开&#x1f7ea;生日快乐⬛早点睡觉 &#x1f4d8;博主相关 &#x1f7e7;博主信息&#x1f7e8;博客首页&#x1f7eb;专栏推荐&#x1f7e5;活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别 直接训练提示词嵌入向量的核心区别 您提到的代码: prompt_embedding = initial_embedding.clone().requires_grad_(True) optimizer = torch.optim.Adam([prompt_embedding...

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

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

LINUX 69 FTP 客服管理系统 man 5 /etc/vsftpd/vsftpd.conf

FTP 客服管理系统 实现kefu123登录&#xff0c;不允许匿名访问&#xff0c;kefu只能访问/data/kefu目录&#xff0c;不能查看其他目录 创建账号密码 useradd kefu echo 123|passwd -stdin kefu [rootcode caozx26420]# echo 123|passwd --stdin kefu 更改用户 kefu 的密码…...

Webpack性能优化:构建速度与体积优化策略

一、构建速度优化 1、​​升级Webpack和Node.js​​ ​​优化效果​​&#xff1a;Webpack 4比Webpack 3构建时间降低60%-98%。​​原因​​&#xff1a; V8引擎优化&#xff08;for of替代forEach、Map/Set替代Object&#xff09;。默认使用更快的md4哈希算法。AST直接从Loa…...

毫米波雷达基础理论(3D+4D)

3D、4D毫米波雷达基础知识及厂商选型 PreView : https://mp.weixin.qq.com/s/bQkju4r6med7I3TBGJI_bQ 1. FMCW毫米波雷达基础知识 主要参考博文&#xff1a; 一文入门汽车毫米波雷达基本原理 &#xff1a;https://mp.weixin.qq.com/s/_EN7A5lKcz2Eh8dLnjE19w 毫米波雷达基础…...

ubuntu22.04有线网络无法连接,图标也没了

今天突然无法有线网络无法连接任何设备&#xff0c;并且图标都没了 错误案例 往上一顿搜索&#xff0c;试了很多博客都不行&#xff0c;比如 Ubuntu22.04右上角网络图标消失 最后解决的办法 下载网卡驱动&#xff0c;重新安装 操作步骤 查看自己网卡的型号 lspci | gre…...