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

【算法】前缀和

作者:指针不指南吗
专栏:算法篇

🐾要学会在纸上打草稿,这个很重要🐾

文章目录

    • 1.什么是前缀和?
    • 2.怎么求前缀和?
    • 3.前缀和有什么用?
    • 4.进阶二维:矩阵和

前缀和 主打一个记公式

1.什么是前缀和?

原数组

a1 , a2 , a3 , a4 , a5 , a6 , a7

前缀和

s1=a1;

s2=a1+a2;

s3=a1+a2+a3;

si=a1+a2+a3+…+ai

前缀和实际就是数组前 i 项和


2.怎么求前缀和?

结合定义,解释的很清楚,前 i 项相加即可

思路:第 i 个前缀和就 = 前一个前缀和 + 第 i 个元素

但是注意!!!循环开始从1开始,s0=0;

  • 第一种

    易懂但用两个数组

for(int i=1;i<=n;i++){scanf("%d",&a[i]);s[i]+=a[i];}
  • 第二种

    优化版:只需要一个数组

for(int i=1;i<=;i++){scanf("%d",&s[i]);s[i]+=s[i-1];}

3.前缀和有什么用?

作用只有一个:求区间和

求区间使用前缀和可以降低时间复杂度,更加方便

求区间[l,r]中元素的和:

s [ l ~ r ] = s [ r ] - s [ l -1 ]

这里解释了为什么写前缀和的时候,从1开始,并且s0=0 通用的,对 s[1~

n]也适用

例如,求数组第a个到第b个的子数组的和

 while(m--){int a,b;cin>>a>>b;cout<<s[b]-s[a-1]<<endl;}

4.进阶二维:矩阵和

求黄色部分的子矩阵和

黄=整个-绿-蓝+混

S[i, j] = 第i行j列格子左上部分所有元素的和

以(x1, y1)为左上角,(x2, y2)为右下角的子矩阵的和为:

S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]

  • 代码实现
#include<iostream>
using namespace std;const int N=1010;int s[N][N];int n,m,q;int main(){cin>>n>>m>>q;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){cin>>s[i][j];s[i][j]+=s[i-1][j]+s[i][j-1]+s[i-1][j-1];}while(q--){int x1,y1,x2,y2;cin>>x1>>y1>>x2>>y2;cout<<s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1];}return 0;
}

相关文章:

【算法】前缀和

作者&#xff1a;指针不指南吗 专栏&#xff1a;算法篇 &#x1f43e;要学会在纸上打草稿&#xff0c;这个很重要&#x1f43e; 文章目录1.什么是前缀和&#xff1f;2.怎么求前缀和&#xff1f;3.前缀和有什么用&#xff1f;4.进阶二维:矩阵和前缀和 主打一个记公式 1.什么是前…...

《Redis实战篇》七、Redis消息队列

7.1 Redis消息队列-认识消息队列 什么是消息队列&#xff1a;字面意思就是存放消息的队列。最简单的消息队列模型包括3个角色&#xff1a; 消息队列&#xff1a;存储和管理消息&#xff0c;也被称为消息代理&#xff08;Message Broker&#xff09;生产者&#xff1a;发送消息…...

android组件化

学习流程&#xff1a;1.开源最佳实践&#xff1a;Android平台页面路由框架ARouter-阿里云开发者社区 (aliyun.com)2.中文ARouter使用API&#xff1a;https://github.com/alibaba/ARouter/blob/master/README_CN.md3.看当前文档后面的代码4.这是通俗易懂的文章&#xff1a;https…...

华为OD机试真题Python实现【特异性双端队列】真题+解题思路+代码(20222023)

🔥系列专栏 华为OD机试(Python)真题目录汇总华为OD机试(JAVA)真题目录汇总华为OD机试(C++)真题目录汇总华为OD机试(JavaScript)真题目录汇总文章目录 🔥系列专栏题目输入输出示例一输入输出解题思路核心知识点Python 代码实现代码运行结果版权说明<...

24.架构能力

文章目录24. 架构能力24.1 Competence of Individuals: Duties, Skills, and Knowledge of Architects 个人能力&#xff1a;架构师的职责、技能和知识24.2 Competence of a Software Architecture Organization 软件架构组织的能力24.3 Summary 小结24.4 For Further Reading …...

前端原生 CSS 跑马灯效果,无限轮播(横竖版本,带渐变遮罩,简单实用)

一、横版跑马灯 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta http-equiv"X-UA-Compatible" content"IEedge"><meta name"viewport" content"widthdevice-wid…...

4.8 注解与自定义注解

文章目录1.概述2.注解的分类2.1 JDK注解2.2 元注解2.2.1 Target ElementType…2.2.2 Retention RetentionPolicy…3 自定义注解1.概述 在注解刚出现时&#xff0c;曾受到过好多程序员的鄙夷&#xff0c;觉得这就是多此一举的操作&#xff1b; 但随着时间的推移&#xff0c;越…...

webpack 的热更新是如何做到的?原理是什么?

Hot Module Replacement&#xff0c;简称 HMR&#xff0c;在不需要刷新整个页面的同时更新模块&#xff0c;能够提升开发的效率和体验。热更新时只会局部刷新页面上发生了变化的模块&#xff0c;同时可以保留当前页面的状态&#xff0c;比如复选框的选中状态等。 在 webpack 中…...

嵌入式ARM设计编程(一) 简单数据搬移

文章和代码已归档至【Github仓库&#xff1a;hardware-tutorial】&#xff0c;需要的朋友们自取。或者公众号【AIShareLab】回复 嵌入式 也可获取。 一、实验目的 熟悉实验开发环境&#xff0c;掌握简单ARM汇编指令的使用方法。 二、实验环境 硬件&#xff1a;PC机 软件&am…...

【Selenium】十分钟手把手带你学会WebDriver API

目录 1、定位元素【8种】 2、操作测试对象 3、添加等待 4、弹窗类型 5、浏览器的操作 6、键盘事件 7、选择框 8、上传文件 1、定位元素【8种】 元素定位是自动化测试的核心&#xff0c;想要去操作一个对象&#xff0c;第一步就是需要我们先去识别这个对象。每个对象就会…...

3DMAX高级弯曲插件使用教程

3dMax高级弯曲插件是对3dmax原生“弯曲&#xff08;Bend&#xff09;”修改器的一个增强&#xff0c;给用户更多控制弯曲修改器的参数设置&#xff0c;它让用户输入宽度&#xff0c;插件脚本将移动中心以获得正确的宽度。 主要特性&#xff1a; - 使用智能捕捉捕捉到自定义网格…...

前端面试题之性能优化大杂烩

主要内容为下面几大类&#xff1a;移动端、图片、JavaScript、css、html、页面内容、服务器、cookie。 移动端性能优化&#xff1a; 保持单个文件小于25KB 移动网站页面要求下载资源&#xff0c;如果文件过大&#xff0c;会大大减慢页面加载速度。 打包内容为分段multipart文…...

SpringBoot+Vue实现养老智慧服务平台

文末获取源码 开发语言&#xff1a;Java 框架&#xff1a;springboot JDK版本&#xff1a;JDK1.8 服务器&#xff1a;tomcat7 数据库&#xff1a;mysql 5.7/8.0 数据库工具&#xff1a;Navicat11 开发软件&#xff1a;eclipse/myeclipse/idea Maven包&#xff1a;Maven3.3.9 浏…...

tigervnc2023

sudo apt-get install tigervnc-standalone-server 配置用户 /etc/tigervnc/vncserver.users :1user1 :2user2 :3user3 全局配置 /etc/tigervnc/vncserver-config-defaults $localhost"no"; $geometry "1920x1200"; 分别进入user1 user2 user3 用户…...

智能三子棋(人机大战)—— 你会是最终赢家吗?万字讲解让你实现与自己对弈

魔王的介绍&#xff1a;&#x1f636;‍&#x1f32b;️一名双非本科大一小白。魔王的目标&#xff1a;&#x1f92f;努力赶上周围卷王的脚步。魔王的主页&#xff1a;&#x1f525;&#x1f525;&#x1f525;大魔王.&#x1f525;&#x1f525;&#x1f525; ❤️‍&#x1…...

【自制开发板】自制STM32F407开发板(含TFT 8080串口屏幕接口)

【2023 年 2 月 14 日】 许久没有更新&#xff0c;最近做了个小开发板玩了玩。更新一下吧&#xff0c;作为记录&#xff01;&#xff01; 主要是象试一下LVGL在STM32上的应用&#xff0c;所以开发板的大小都是基于屏幕大小来设计的。 分享出来&#xff0c;给大家一个板子结构…...

openvino yolov5/ssd 实时推流目标检测在html上显示

安装ffmepg并添加到环境变量中&#xff0c;流媒体使用m7s 运行效果 SSD&#xff1a;检测在10ms左右&#xff0c;yolov5在100ms左右 app.py #!/usr/local/bin/python3 # encodin: utf-8import subprocess import threading import time import cv2 import osfrom OpenVinoYoloV…...

基于FPGA的 SPI通信 设计(1)

引言 低速通信目前搞过 UART串口通信、IIC通信。其实 SPI 也算是中低速&#xff08;有时也可以用作高速通信&#xff09;串行通信的范畴&#xff0c;但是一直还没真正实现过&#xff0c;所以此系列就 SPI的协议以及FPGA设计作几篇博客记录。欢迎订阅关注~ SPI 标准协议 x1模式…...

为什么西门子、美的等企业这样进行架构升级,看看改造效果就知道了

在工业领域&#xff0c; 生产、测试、运行阶段都可能会产生大量带有时间戳的传感器数据&#xff0c;这都属于典型的时序数据。时序数据主要由各类型实时监测、检查与分析设备所采集或产生&#xff0c;涉及制造、电力、化工、工程作业等多个行业&#xff0c;具备写多读少、量非常…...

open3d点云配准函数registration_icp

文章目录基本原理open3d调用绘图基本原理 ICP, 即Iterative Closest Point, 迭代点算法。 ICP算法有多种形式&#xff0c;其中最简单的思路就是比较点与点之间的距离&#xff0c;对于点云P{pi},Q{qi}P\{p_i\}, Q\{q_i\}P{pi​},Q{qi​}而言&#xff0c;如果二者是同一目标&am…...

千万级数据表优化:分库分表、分区、索引最佳实践生产实战

本文适合&#xff1a;后端开发、DBA、面试准备、线上性能调优。全文干货无废话&#xff0c;覆盖索引设计、分区实战、分库分表落地、生产踩坑&#xff0c;可直接发布 CSDN。 前言 在互联网业务高速增长的今天&#xff0c;单表数据量突破千万、甚至上亿已经非常普遍。很多项目初…...

【仅限首批读者】FastAPI 2.0流式响应私密配置手册:隐藏在testclient源码中的3个async test陷阱与真实压测调优参数

第一章&#xff1a;FastAPI 2.0流式响应的核心演进与设计哲学FastAPI 2.0 将流式响应&#xff08;StreamingResponse&#xff09;从一种边缘支持的扩展能力&#xff0c;提升为框架原生、类型安全且可组合的一等公民。这一转变并非简单功能叠加&#xff0c;而是源于对现代 API 架…...

Phi-4-mini-reasoning参数调优:最大输出长度1024对多步推理完整性的影响

Phi-4-mini-reasoning参数调优&#xff1a;最大输出长度1024对多步推理完整性的影响 1. 模型概述 Phi-4-mini-reasoning是一款专注于推理任务的文本生成模型&#xff0c;特别适合处理需要多步分析的复杂问题。与通用聊天模型不同&#xff0c;它被设计用于数学题解答、逻辑推理…...

GoJieba自定义词典使用指南:3步添加专业领域词汇的终极方法

GoJieba自定义词典使用指南&#xff1a;3步添加专业领域词汇的终极方法 【免费下载链接】gojieba "结巴"中文分词的Golang版本 项目地址: https://gitcode.com/gh_mirrors/go/gojieba GoJieba是"结巴"中文分词的Golang版本&#xff0c;作为一款高效…...

华为设备静态路由与BFD联动实战:从配置到故障切换全解析

1. 为什么需要BFD与静态路由联动&#xff1f; 静态路由就像一张纸质地图&#xff0c;一旦画好就不会自动更新。当某条道路&#xff08;网络链路&#xff09;突然塌方时&#xff0c;纸质地图不会自动标注"此路不通"&#xff0c;司机&#xff08;数据包&#xff09;还是…...

终极英语写作助手:write-good帮你避免10个常见语法错误

终极英语写作助手&#xff1a;write-good帮你避免10个常见语法错误 【免费下载链接】write-good Naive linter for English prose 项目地址: https://gitcode.com/gh_mirrors/wr/write-good write-good 是一个专为开发者设计的英语写作语法检查工具&#xff0c;能够智能…...

OpenClaw安全防护指南:Qwen3-14B私有镜像下的权限管控实践

OpenClaw安全防护指南&#xff1a;Qwen3-14B私有镜像下的权限管控实践 1. 为什么需要关注OpenClaw的安全防护&#xff1f; 去年我在尝试用OpenClaw自动化处理财务报表时&#xff0c;曾遭遇过一次"惊魂时刻"——脚本误将未加密的财务数据上传到了临时目录。这次经历…...

OpenClaw定时任务配置:Phi-3-mini-128k-instruct每日早报自动生成

OpenClaw定时任务配置&#xff1a;Phi-3-mini-128k-instruct每日早报自动生成 1. 为什么需要自动化早报服务 每天早上打开电脑第一件事&#xff0c;就是花20分钟浏览各大新闻网站&#xff0c;手动整理成简报发到团队群。这种重复劳动持续三个月后&#xff0c;我开始思考&…...

基于Qwen3.5-2B的数据库课程设计智能指导系统

基于Qwen3.5-2B的数据库课程设计智能指导系统 1. 课程设计的痛点与解决方案 每到学期末&#xff0c;计算机专业的学生们都会面临一个共同的挑战——数据库课程设计。从选题到ER图设计&#xff0c;再到SQL编写和报告撰写&#xff0c;整个过程往往让学生们感到无从下手。传统的…...

YOLOv11检测头实战:在自定义数据集上提升小目标检测精度的保姆级调参指南

YOLOv11检测头实战&#xff1a;在自定义数据集上提升小目标检测精度的保姆级调参指南 当你在工业质检流水线上发现微小缺陷频繁漏检&#xff0c;或是遥感图像中的小型目标难以捕捉时&#xff0c;传统检测算法的局限性就暴露无遗。YOLOv11的检测头革新为这些痛点提供了专业级解决…...