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

前缀和差分

前缀和

前缀和:一段序列里的前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

111111

差分数组difference

100000

此时,L=2,R=4,X=1

操作方式:difference[L]=difference[L]+X,影响L之后的数字

                  difference[R+1]=difference[R+1]-X,避免影响R+1以及之后的数字

操作后的差分数组difference

1100-10

还原后的数组arr

122211

二维差分

一维差分修改差分数组中的某个数,影响的是原数组它本身及其之后的数

二维差分修改差分数组中的某个数,影响的是原数组它本身及其右下角全部的数

二维差分的应用:对以 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.按照测试对象划分 ①界面测试 软件只是一种工具,软件与人的信息交流是通过界面来进行的,界面是软件与用户交流的最直接的一层,界面的设计决定了用户对设计的软件的第一印象。界面如同人的面孔,具有吸引用户的直接优势&#xf…...

打开域名跳转其他网站,官网被黑解决方案(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)

一&#xff0c;在Kubernetes上部署istio 在Kubernetes上部署istio&#xff0c;可以按照以下步骤进行&#xff1a; 安装Istio 使用以下命令从Istio官网下载最新版本的Istio&#xff1a; curl -L https://istio.io/downloadIstio | ISTIO_VERSION<VERSION> sh - 其中&…...

Golang 获取本地 IP 地址方法

在 Golang 中&#xff0c;使用 net 包可以很方便地获取到本机IP地址。 借助 net.InterfaceAddrs 方法 简单示例代码如下&#xff1a; package mainimport ("fmt""net" )func main() {addrList, err : net.InterfaceAddrs()if err ! nil {panic(err)}for…...

抖音seo短视频账号矩阵系统技术开发简述

说明&#xff1a;本开发文档适用于抖音seo源码开发&#xff0c;抖音矩阵系统开发&#xff0c;短视频seo源码开发&#xff0c;短视频矩阵系统源码开发 一、 抖音seo短视频矩阵系统开发包括 抖音seo短视频账号矩阵系统的技术开发主要包括以下几个方面&#xff1a; 1.前端界面设…...

运维高级--shell脚本完成分库分表

为什么要进行分库分表 随着系统的运行&#xff0c;存储的数据量会越来越大&#xff0c;系统的访问的压力也会随之增大&#xff0c;如果一个库中的表数据超过了一定的数量&#xff0c;比如说MySQL中的表数据达到千万级别&#xff0c;就需要考虑进行分库分表&#xff1b; 其…...

Mysql 忘记密码怎么重置密码(详细步骤)

每种方法都有其适用的情况&#xff0c;根据具体情况选择合适的方法。无论选择哪种方法&#xff0c;请务必在重置密码后及时删除临时用户并重新启动 MySQL 服务。 一、使用 mysqladmin 重置密码 停止服务 # systemctl 启动的使用这个停止 $ sudo systemctl stop mysql# mac 本机…...

机器学习深度学习——图像分类数据集

&#x1f468;‍&#x1f393;作者简介&#xff1a;一位即将上大四&#xff0c;正专攻机器学习的保研er &#x1f30c;上期文章&#xff1a;机器学习&&深度学习——softmax回归&#xff08;下&#xff09; &#x1f4da;订阅专栏&#xff1a;机器学习&&深度学习…...

【PWN · 栈迁移】[BUUCTF]ciscn_2019_es_2

第一道栈迁移题目&#xff0c;跌跌撞撞理解了 前言 当前溢出可用空间比较少时&#xff08;极端情况下仅能覆写ebp和ret&#xff09;&#xff0c;可以通过栈迁移的方式&#xff0c;扩大shellcode的容纳空间&#xff0c;其核心是将esp移动到一段shellocode开头。而esp总是由ebp赋…...

CTF show Web 红包题第六弹

提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框&#xff0c;很难让人不联想到SQL注入&#xff0c;但提示都说了不是SQL注入&#xff0c;所以就不往这方面想了 ​ 先查看一下网页源码&#xff0c;发现一段JavaScript代码&#xff0c;有一个关键类ctfs…...

Spring Boot 实现流式响应(兼容 2.7.x)

在实际开发中&#xff0c;我们可能会遇到一些流式数据处理的场景&#xff0c;比如接收来自上游接口的 Server-Sent Events&#xff08;SSE&#xff09; 或 流式 JSON 内容&#xff0c;并将其原样中转给前端页面或客户端。这种情况下&#xff0c;传统的 RestTemplate 缓存机制会…...

在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能

下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能&#xff0c;包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...

以下是对华为 HarmonyOS NETX 5属性动画(ArkTS)文档的结构化整理,通过层级标题、表格和代码块提升可读性:

一、属性动画概述NETX 作用&#xff1a;实现组件通用属性的渐变过渡效果&#xff0c;提升用户体验。支持属性&#xff1a;width、height、backgroundColor、opacity、scale、rotate、translate等。注意事项&#xff1a; 布局类属性&#xff08;如宽高&#xff09;变化时&#…...

Qt Widget类解析与代码注释

#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this); }Widget::~Widget() {delete ui; }//解释这串代码&#xff0c;写上注释 当然可以&#xff01;这段代码是 Qt …...

visual studio 2022更改主题为深色

visual studio 2022更改主题为深色 点击visual studio 上方的 工具-> 选项 在选项窗口中&#xff0c;选择 环境 -> 常规 &#xff0c;将其中的颜色主题改成深色 点击确定&#xff0c;更改完成...

YSYX学习记录(八)

C语言&#xff0c;练习0&#xff1a; 先创建一个文件夹&#xff0c;我用的是物理机&#xff1a; 安装build-essential 练习1&#xff1a; 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件&#xff0c;随机修改或删除一部分&#xff0c;之后…...

CentOS下的分布式内存计算Spark环境部署

一、Spark 核心架构与应用场景 1.1 分布式计算引擎的核心优势 Spark 是基于内存的分布式计算框架&#xff0c;相比 MapReduce 具有以下核心优势&#xff1a; 内存计算&#xff1a;数据可常驻内存&#xff0c;迭代计算性能提升 10-100 倍&#xff08;文档段落&#xff1a;3-79…...

自然语言处理——Transformer

自然语言处理——Transformer 自注意力机制多头注意力机制Transformer 虽然循环神经网络可以对具有序列特性的数据非常有效&#xff0c;它能挖掘数据中的时序信息以及语义信息&#xff0c;但是它有一个很大的缺陷——很难并行化。 我们可以考虑用CNN来替代RNN&#xff0c;但是…...

让AI看见世界:MCP协议与服务器的工作原理

让AI看见世界&#xff1a;MCP协议与服务器的工作原理 MCP&#xff08;Model Context Protocol&#xff09;是一种创新的通信协议&#xff0c;旨在让大型语言模型能够安全、高效地与外部资源进行交互。在AI技术快速发展的今天&#xff0c;MCP正成为连接AI与现实世界的重要桥梁。…...