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利用以太网开发智能液位检测仪 目前,工业以太网接口在国内外的发展已经达到了相当深入的程度,特别是在自动化控制和工业控制领域有着非常广泛的应用。在工业生产过程中,钢厂的连铸机是前后的连接环节,其中钢水从大钢包进入…...
Python爬虫实战:研究MechanicalSoup库相关技术
一、MechanicalSoup 库概述 1.1 库简介 MechanicalSoup 是一个 Python 库,专为自动化交互网站而设计。它结合了 requests 的 HTTP 请求能力和 BeautifulSoup 的 HTML 解析能力,提供了直观的 API,让我们可以像人类用户一样浏览网页、填写表单和提交请求。 1.2 主要功能特点…...
DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径
目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...

《Qt C++ 与 OpenCV:解锁视频播放程序设计的奥秘》
引言:探索视频播放程序设计之旅 在当今数字化时代,多媒体应用已渗透到我们生活的方方面面,从日常的视频娱乐到专业的视频监控、视频会议系统,视频播放程序作为多媒体应用的核心组成部分,扮演着至关重要的角色。无论是在个人电脑、移动设备还是智能电视等平台上,用户都期望…...
Java 8 Stream API 入门到实践详解
一、告别 for 循环! 传统痛点: Java 8 之前,集合操作离不开冗长的 for 循环和匿名类。例如,过滤列表中的偶数: List<Integer> list Arrays.asList(1, 2, 3, 4, 5); List<Integer> evens new ArrayList…...

基于Flask实现的医疗保险欺诈识别监测模型
基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施,由雇主和个人按一定比例缴纳保险费,建立社会医疗保险基金,支付雇员医疗费用的一种医疗保险制度, 它是促进社会文明和进步的…...

ServerTrust 并非唯一
NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...

QT: `long long` 类型转换为 `QString` 2025.6.5
在 Qt 中,将 long long 类型转换为 QString 可以通过以下两种常用方法实现: 方法 1:使用 QString::number() 直接调用 QString 的静态方法 number(),将数值转换为字符串: long long value 1234567890123456789LL; …...
[Java恶补day16] 238.除自身以外数组的乘积
给你一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法,且在 O(n) 时间复杂度…...

OPenCV CUDA模块图像处理-----对图像执行 均值漂移滤波(Mean Shift Filtering)函数meanShiftFiltering()
操作系统:ubuntu22.04 OpenCV版本:OpenCV4.9 IDE:Visual Studio Code 编程语言:C11 算法描述 在 GPU 上对图像执行 均值漂移滤波(Mean Shift Filtering),用于图像分割或平滑处理。 该函数将输入图像中的…...

VM虚拟机网络配置(ubuntu24桥接模式):配置静态IP
编辑-虚拟网络编辑器-更改设置 选择桥接模式,然后找到相应的网卡(可以查看自己本机的网络连接) windows连接的网络点击查看属性 编辑虚拟机设置更改网络配置,选择刚才配置的桥接模式 静态ip设置: 我用的ubuntu24桌…...