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

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 循环&#xff01; 传统痛点&#xff1a; Java 8 之前&#xff0c;集合操作离不开冗长的 for 循环和匿名类。例如&#xff0c;过滤列表中的偶数&#xff1a; List<Integer> list Arrays.asList(1, 2, 3, 4, 5); List<Integer> evens new ArrayList…...

基于Flask实现的医疗保险欺诈识别监测模型

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

ServerTrust 并非唯一

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

QT: `long long` 类型转换为 `QString` 2025.6.5

在 Qt 中&#xff0c;将 long long 类型转换为 QString 可以通过以下两种常用方法实现&#xff1a; 方法 1&#xff1a;使用 QString::number() 直接调用 QString 的静态方法 number()&#xff0c;将数值转换为字符串&#xff1a; long long value 1234567890123456789LL; …...

[Java恶补day16] 238.除自身以外数组的乘积

给你一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O(n) 时间复杂度…...

OPenCV CUDA模块图像处理-----对图像执行 均值漂移滤波(Mean Shift Filtering)函数meanShiftFiltering()

操作系统&#xff1a;ubuntu22.04 OpenCV版本&#xff1a;OpenCV4.9 IDE:Visual Studio Code 编程语言&#xff1a;C11 算法描述 在 GPU 上对图像执行 均值漂移滤波&#xff08;Mean Shift Filtering&#xff09;&#xff0c;用于图像分割或平滑处理。 该函数将输入图像中的…...

VM虚拟机网络配置(ubuntu24桥接模式):配置静态IP

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