前缀和差分
前缀和
前缀和:一段序列里的前n项和
给出n个数,在给出q次问询,每次问询给出L、R,快速求出每组数组中一段L至R区间的和
给出一段数组,每次问询为求出l到r区间的和
普通方法:L到R进行遍历,那么在每次求区间和的过程中时间复杂度为O(n),q次问询时间复杂度为O(q*n)
前缀和:建立前缀和数组,sum[i]=sum[i-1]+arr[i]。(i-1存在越界的问题,所以i从1开始遍历)
计算L到R的区间和,包括arr[L]和arr[R]两个值(边界值),区间和=arr[R]-arr[L-1]
时间复杂度从O(q*n)降至O(q*1)
二维前缀和
二维前缀和数组是原数组它本身位置的数及其左上角全部的数

二维前缀和的应用:求二维数组中arr[x1][y1]到arr[x2][y2]区间内的数之和
差分
给出n个数,再给出q次问询,每次问询给出L、R、X,要求在L到R上每一个值都加上X,直到最后输出这个数组
普通方法:遍历,时间复杂度为O(q*n)
差分:建立差分数组,difference[i]=arr[i]-arr[i-1],arr[i]=difference[i]+arr[i-1]。
(同样i从1开始遍历)
时间复杂度从O(q*n)降至O(q*1)
数组arr
| 1 | 1 | 1 | 1 | 1 | 1 |
差分数组difference
| 1 | 0 | 0 | 0 | 0 | 0 |
此时,L=2,R=4,X=1
操作方式:difference[L]=difference[L]+X,影响L之后的数字
difference[R+1]=difference[R+1]-X,避免影响R+1以及之后的数字
操作后的差分数组difference
| 1 | 1 | 0 | 0 | -1 | 0 |
还原后的数组arr
| 1 | 2 | 2 | 2 | 1 | 1 |
二维差分
一维差分修改差分数组中的某个数,影响的是原数组它本身及其之后的数
二维差分修改差分数组中的某个数,影响的是原数组它本身及其右下角全部的数
二维差分的应用:对以 x1, y1 为左上角, x2, y2 为右下角的矩阵插入一个值 / 修改值

相关文章:
前缀和差分
前缀和 前缀和:一段序列里的前n项和 给出n个数,在给出q次问询,每次问询给出L、R,快速求出每组数组中一段L至R区间的和 给出一段数组,每次问询为求出l到r区间的和 普通方法:L到R进行遍历,那么…...
Golang GORM 模型定义
模型定义 参考文档:https://gorm.io/zh_CN/docs/models.html 模型一般都是普通的 Golang 的结构体,Go的基本数据类型,或者指针。 模型是标准的struct,由Go的基本数据类型、实现了Scanner和Valuer接口的自定义类型及其指针或别名组成&#x…...
微服务的各种边界在架构演进中的作用
演进式架构 在微服务设计和实施的过程中,很多人认为:“将单体拆分成多少个微服务,是微服务的设计重点。”可事实真的是这样吗?其实并非如此! Martin Fowler 在提出微服务时,他提到了微服务的一个重要特征—…...
使用 docker-compose 一键部署多个 redis 实例
目录 1. 前期准备 2. 导入镜像 3. 部署redis master脚本 4. 部署redis slave脚本 5. 模板文件 6. 部署redis 7. 基本维护 1. 前期准备 新部署前可以从仓库(repository)下载 redis 镜像,或者从已有部署中的镜像生成文件: …...
14-测试分类
1.按照测试对象划分 ①界面测试 软件只是一种工具,软件与人的信息交流是通过界面来进行的,界面是软件与用户交流的最直接的一层,界面的设计决定了用户对设计的软件的第一印象。界面如同人的面孔,具有吸引用户的直接优势…...
打开域名跳转其他网站,官网被黑解决方案(Linux)
某天打开网站,发现进入首页,马上挑战到其他赌博网站。 事不宜迟,不能让客户发现,得马上解决 我的网站跳转到这个域名了 例如网站跳转到 k77.cc 就在你们部署的代码的当前文件夹下面,执行下如下命令 find -type …...
redis总结
1.redis redis高性能的key-value数据库,支持持久化,不仅仅支持简单的key-value,还提供了list,set,zset,hash等数据结构的存储,支持数据的备份(master-slave模式) redis&…...
现代C++中的从头开始深度学习:激活函数
一、说明 让我们通过在C中实现激活函数来获得乐趣。人工神经网络是生物启发模型的一个例子。在人工神经网络中,称为神经元的处理单元被分组在计算层中,通常用于执行模式识别任务。 在这个模型中,我们通常更喜欢控制每一层的输出以服从一些约束…...
python怎么实现tcp和udp连接
目录 什么是tcp连接 什么是udp连接 python怎么实现tcp和udp连接 什么是tcp连接 TCP(Transmission Control Protocol)连接是一种网络连接,它提供了可靠的、面向连接的数据传输服务。 在TCP连接中,通信的两端(客户端和…...
java设计模式-观察者模式(jdk内置)
上一篇我们学习了 观察者模式。 观察者和被观察者接口都是我们自己定义的,整个设计模式我们从无到有都是自己设计的,其实,java已经内置了这个设计模式,我们只需要定义实现类即可。 下面我们不多说明,直接示例代码&am…...
秒级体验本地调试远程 k8s 中的服务
点击上方蓝色字体,选择“设为星标” 回复”云原生“获取基础架构实践 背景 在这个以k8s为云os的时代,程序员在日常的开发过程中,肯定会遇到各种问题,比如:本地开发完,需要部署到远程k8s集群,本地…...
CV前沿方向:Visual Prompting 视觉提示工程下的范式
prompt在视觉领域,也越来越重要,在图像生成,作为一种可控条件,增进交互和可控性,在多模态理解方面,指令prompt也使得任务灵活通用。视觉提示工程,已然成为CV一个前沿方向! 下面来看看…...
Redis五大基础类型解析
1.String类型 特征:即存储字符串的类型,单个字符串存储量最大不超过512MB 常用业务场景:⽤来存储JSON序列化之后对象 底层编码: int编码 数据结构特点:ptr指针直接指向字符串常量池中对应字符串地址,而…...
在CSDN学Golang云原生(服务网格istio)
一,在Kubernetes上部署istio 在Kubernetes上部署istio,可以按照以下步骤进行: 安装Istio 使用以下命令从Istio官网下载最新版本的Istio: curl -L https://istio.io/downloadIstio | ISTIO_VERSION<VERSION> sh - 其中&…...
Golang 获取本地 IP 地址方法
在 Golang 中,使用 net 包可以很方便地获取到本机IP地址。 借助 net.InterfaceAddrs 方法 简单示例代码如下: package mainimport ("fmt""net" )func main() {addrList, err : net.InterfaceAddrs()if err ! nil {panic(err)}for…...
抖音seo短视频账号矩阵系统技术开发简述
说明:本开发文档适用于抖音seo源码开发,抖音矩阵系统开发,短视频seo源码开发,短视频矩阵系统源码开发 一、 抖音seo短视频矩阵系统开发包括 抖音seo短视频账号矩阵系统的技术开发主要包括以下几个方面: 1.前端界面设…...
运维高级--shell脚本完成分库分表
为什么要进行分库分表 随着系统的运行,存储的数据量会越来越大,系统的访问的压力也会随之增大,如果一个库中的表数据超过了一定的数量,比如说MySQL中的表数据达到千万级别,就需要考虑进行分库分表; 其…...
Mysql 忘记密码怎么重置密码(详细步骤)
每种方法都有其适用的情况,根据具体情况选择合适的方法。无论选择哪种方法,请务必在重置密码后及时删除临时用户并重新启动 MySQL 服务。 一、使用 mysqladmin 重置密码 停止服务 # systemctl 启动的使用这个停止 $ sudo systemctl stop mysql# mac 本机…...
机器学习深度学习——图像分类数据集
👨🎓作者简介:一位即将上大四,正专攻机器学习的保研er 🌌上期文章:机器学习&&深度学习——softmax回归(下) 📚订阅专栏:机器学习&&深度学习…...
【PWN · 栈迁移】[BUUCTF]ciscn_2019_es_2
第一道栈迁移题目,跌跌撞撞理解了 前言 当前溢出可用空间比较少时(极端情况下仅能覆写ebp和ret),可以通过栈迁移的方式,扩大shellcode的容纳空间,其核心是将esp移动到一段shellocode开头。而esp总是由ebp赋…...
UE5 学习系列(二)用户操作界面及介绍
这篇博客是 UE5 学习系列博客的第二篇,在第一篇的基础上展开这篇内容。博客参考的 B 站视频资料和第一篇的链接如下: 【Note】:如果你已经完成安装等操作,可以只执行第一篇博客中 2. 新建一个空白游戏项目 章节操作,重…...
JavaSec-RCE
简介 RCE(Remote Code Execution),可以分为:命令注入(Command Injection)、代码注入(Code Injection) 代码注入 1.漏洞场景:Groovy代码注入 Groovy是一种基于JVM的动态语言,语法简洁,支持闭包、动态类型和Java互操作性,…...
云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?
大家好,欢迎来到《云原生核心技术》系列的第七篇! 在上一篇,我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在,我们就像一个拥有了一块崭新数字土地的农场主,是时…...
阿里云ACP云计算备考笔记 (5)——弹性伸缩
目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...
为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?
在建筑行业,项目管理的重要性不言而喻。随着工程规模的扩大、技术复杂度的提升,传统的管理模式已经难以满足现代工程的需求。过去,许多企业依赖手工记录、口头沟通和分散的信息管理,导致效率低下、成本失控、风险频发。例如&#…...
【OSG学习笔记】Day 16: 骨骼动画与蒙皮(osgAnimation)
骨骼动画基础 骨骼动画是 3D 计算机图形中常用的技术,它通过以下两个主要组件实现角色动画。 骨骼系统 (Skeleton):由层级结构的骨头组成,类似于人体骨骼蒙皮 (Mesh Skinning):将模型网格顶点绑定到骨骼上,使骨骼移动…...
python执行测试用例,allure报乱码且未成功生成报告
allure执行测试用例时显示乱码:‘allure’ �����ڲ����ⲿ���Ҳ���ǿ�&am…...
HarmonyOS运动开发:如何用mpchart绘制运动配速图表
##鸿蒙核心技术##运动开发##Sensor Service Kit(传感器服务)# 前言 在运动类应用中,运动数据的可视化是提升用户体验的重要环节。通过直观的图表展示运动过程中的关键数据,如配速、距离、卡路里消耗等,用户可以更清晰…...
基于TurtleBot3在Gazebo地图实现机器人远程控制
1. TurtleBot3环境配置 # 下载TurtleBot3核心包 mkdir -p ~/catkin_ws/src cd ~/catkin_ws/src git clone -b noetic-devel https://github.com/ROBOTIS-GIT/turtlebot3.git git clone -b noetic https://github.com/ROBOTIS-GIT/turtlebot3_msgs.git git clone -b noetic-dev…...
VM虚拟机网络配置(ubuntu24桥接模式):配置静态IP
编辑-虚拟网络编辑器-更改设置 选择桥接模式,然后找到相应的网卡(可以查看自己本机的网络连接) windows连接的网络点击查看属性 编辑虚拟机设置更改网络配置,选择刚才配置的桥接模式 静态ip设置: 我用的ubuntu24桌…...
