前缀和差分
前缀和
前缀和:一段序列里的前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. 新建一个空白游戏项目 章节操作,重…...
多模态2025:技术路线“神仙打架”,视频生成冲上云霄
文|魏琳华 编|王一粟 一场大会,聚集了中国多模态大模型的“半壁江山”。 智源大会2025为期两天的论坛中,汇集了学界、创业公司和大厂等三方的热门选手,关于多模态的集中讨论达到了前所未有的热度。其中,…...
Java 8 Stream API 入门到实践详解
一、告别 for 循环! 传统痛点: Java 8 之前,集合操作离不开冗长的 for 循环和匿名类。例如,过滤列表中的偶数: List<Integer> list Arrays.asList(1, 2, 3, 4, 5); List<Integer> evens new ArrayList…...
STM32F4基本定时器使用和原理详解
STM32F4基本定时器使用和原理详解 前言如何确定定时器挂载在哪条时钟线上配置及使用方法参数配置PrescalerCounter ModeCounter Periodauto-reload preloadTrigger Event Selection 中断配置生成的代码及使用方法初始化代码基本定时器触发DCA或者ADC的代码讲解中断代码定时启动…...
页面渲染流程与性能优化
页面渲染流程与性能优化详解(完整版) 一、现代浏览器渲染流程(详细说明) 1. 构建DOM树 浏览器接收到HTML文档后,会逐步解析并构建DOM(Document Object Model)树。具体过程如下: (…...
【论文笔记】若干矿井粉尘检测算法概述
总的来说,传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度,通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...
微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据
微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据 Power Query 具有大量专门帮助您清理和准备数据以供分析的功能。 您将了解如何简化复杂模型、更改数据类型、重命名对象和透视数据。 您还将了解如何分析列,以便知晓哪些列包含有价值的数据,…...
基于PHP的连锁酒店管理系统
有需要请加文章底部Q哦 可远程调试 基于PHP的连锁酒店管理系统 一 介绍 连锁酒店管理系统基于原生PHP开发,数据库mysql,前端bootstrap。系统角色分为用户和管理员。 技术栈 phpmysqlbootstrapphpstudyvscode 二 功能 用户 1 注册/登录/注销 2 个人中…...
0x-3-Oracle 23 ai-sqlcl 25.1 集成安装-配置和优化
是不是受够了安装了oracle database之后sqlplus的简陋,无法删除无法上下翻页的苦恼。 可以安装readline和rlwrap插件的话,配置.bahs_profile后也能解决上下翻页这些,但是很多生产环境无法安装rpm包。 oracle提供了sqlcl免费许可,…...
第一篇:Liunx环境下搭建PaddlePaddle 3.0基础环境(Liunx Centos8.5安装Python3.10+pip3.10)
第一篇:Liunx环境下搭建PaddlePaddle 3.0基础环境(Liunx Centos8.5安装Python3.10pip3.10) 一:前言二:安装编译依赖二:安装Python3.10三:安装PIP3.10四:安装Paddlepaddle基础框架4.1…...
