【数据结构】线段树(点修区查)
数据结构-线段树(点修区查)
前置知识
- 分治
- 递归
- 二叉树
思路
我们需要维护一个支持单点修改,区间查询的数据结构,并且要求在线,一般使用线段树解决。
线段树是一个二叉树形的数据结构。
线段树的思想很简单,就是将每个区间分治,构成一个树形结构,从而达到了 log n \log n logn 的时间复杂度。
以下是一个维护最小值的线段树。

具体实现也很简单,如下:
- 建树( build \text{build} build)
从根节点向下遍历,叶节点自更新,非叶节点使用儿子节点更新( pushup \text{pushup} pushup) - 更新( update \text{update} update)
从根节点向下遍历,类似二分查找查找至叶结点,叶节点自更新,非叶节点使用儿子节点更新( pushup \text{pushup} pushup) - 查询( query \text{query} query)
从根节点向下遍历,将区间分治到多个节点上,合并答案。如区间 [ 2 , 6 ] = [ 2 , 3 ] + [ 4 , 5 ] + [ 6 , 6 ] [2,6]=[2,3]+[4,5]+[6,6] [2,6]=[2,3]+[4,5]+[6,6],为节点 5 , 6 , 14 5,6,14 5,6,14 处的答案合并而来。
数据结构参数
- 时间复杂度: O ( n log n ) O(n\log n) O(nlogn)
- 空间复杂度: O ( n ) O(n) O(n)
实现代码
以最小值线段树为例。
int t[MAXN*4];
#define ls p<<1
#define rs p<<1|1
void pushup(int p){t[p]=min(t[ls],t[rs]);
}
void build(int p,int l,int r){if (l==r){t[p]=a[l];return;}int mid=l+r>>1;build(ls,l,mid);build(rs,mid+1,r);pushup(p);
}
void update(int p,int l,int r,int x,int y){if (l==r){t[p]=y;return;}int mid=l+r>>1;if (x<=mid) update(ls,l,mid,x,y);else update(rs,mid+1,r,x,y);pushup(p);
}
int query(int p,int l,int r,int x,int y){if (x<=l&&r<=y) return t[p];int mid=l+r>>1,ans=0x3f3f3f3f;if (x<=l) ans=min(ans,query(ls,l,mid,x,y));else ans=min(ans,query(rs,mid+1,r,x,y));return ans;
}
练习
- 洛谷【模板】树状数组 1
- 洛谷【模板】树状数组 2
因为这个版本的线段树和树状数组差不多。。。
相关文章:
【数据结构】线段树(点修区查)
数据结构-线段树(点修区查) 前置知识 分治递归二叉树 思路 我们需要维护一个支持单点修改,区间查询的数据结构,并且要求在线,一般使用线段树解决。 线段树是一个二叉树形的数据结构。 线段树的思想很简单,…...
Ansys Lumerical | 用于增强现实系统的表面浮雕光栅
在本示例中,我们使用 RCWA 求解器设计了一个斜面浮雕光栅 (SRG),它将用于将光线耦合到单色增强现实 (AR) 系统的波导中。光栅的几何形状经过优化,可将正常入射光导入-1 光栅阶次。 然后我们将光栅特性导出为 Lumerical Sub-Wavelength Model …...
QT day3作业
1.思维导图 2、 完善对话框,点击登录对话框,如果账号和密码匹配,则弹出信息对话框,给出提示”登录成功“,提供一个Ok按钮,用户点击Ok后,关闭登录界面,跳转到其他界面 如果账号和密…...
【Ubuntu】设置永不息屏与安装 dconf-editor
方式一、GUI界面进行设置 No LSB modules are available. Distributor ID: Ubuntu Description: Ubuntu 20.04.6 LTS Release: 20.04 Codename: focal打开 Ubuntu 桌面环境的设置菜单。你可以通过点击屏幕右上角的系统菜单,然后选择设置。在设置菜单中,…...
gRPC 的原理 介绍带你从头了解gRPC
gRPC 的原理 什么是gRPC gRPC的官方介绍是:gRPC是一个现代的、高性能、开源的和语言无关的通用 RPC 框架,基于 HTTP2 协议设计,序列化使用PB(Protocol Buffer),PB 是一种语言无关的高性能序列化框架,基于 HTTP2PB 保…...
Apriori算法
Apriori算法由R. Agrawal和R. Srikant于1994年在数据集中寻找布尔关联规则的频繁项集。该算法的名称是Apriori,因为它使用了频繁项集属性的先验知识。我们应用迭代方法或逐层搜索,其中k-频繁项集用于找到k1个项集。 为了提高频繁项集逐层生成的效率&…...
肖sir__linux讲解(2.1)
linux命令 cp 复制命令 a、cp 原文件名称 新文 件名称(不存在的文件) 案例:cp a k 截图: b.cp 原文件名称 原有文 件名称(存在的文件) 案例:cp a b 截图: c、cp 指定路径复制 格式ÿ…...
The ultimate UI kit and design system for Figma 组件库下载
Untitled UI 是世界上最大的 Figma UI 套件和设计系统。可以启动任何项目,为您节省数千小时,并祝您升级为专业设计师。 采用 100% 自动布局 5.0、变量、智能变体和 WCAG 可访问性精心制作。 900全局样式、变量:超级智能的全局颜色、排版和效…...
Selenium——利用input标签上传文件
Selenium利用input标签上传文件 完整流程 打开文件上传页面选择要上传的文件点击上传按钮确认文件上传成功介绍怎么方便的获取对应元素的Xpath或者Css 简单介绍 在使用Selenium进行浏览器自动化测试时,文件上传是一个常见的需求。而 标签就是实现文件上传功能的…...
C++初阶 日期类的实现(下)
目录 一、输入输出(>>,<<)重载的实现 1.1初始版 1.2友元并修改 1.2.1简单介绍下友元 1.2.2修改 1.3>>重载 二、条件判断操作符的实现 2.1操作符的实现 2.2!操作符的实现 2.3>操作符的实现 2.4>,<,<操作符的实现 三、日期-日期的实现 …...
大师学SwiftUI第16章 - UIKit框架集成
其它相关内容请见虚拟现实(VR)/增强现实(AR)&visionOS开发学习笔记 SwiftUI是一套新框架,因此并没有包含我们构建专业应用所需的所有工具。这意味着我们会需要求助于UIKit(移动设备)和AppKit(Mac电脑)等原…...
7.docker运行redis容器
1.准备redis的配置文件 从上一篇运行MySQL容器我们知道,需要给容器挂载数据卷,来持久化数据和配置,相应的redis也不例外。这里我们以redis6.0.8为例来实际说明下。 1.1 查找redis的配置文件redis.conf 下面这个网址有各种版本的配置文件供…...
unity教程
前言 伴随游戏行业的兴起,unity引擎的使用越来越普遍,本文章主要记录博主本人入门unity的相关记录大部分依赖siki学院进行整理。12 一、认识unity引擎? 1、Unity相关信息: Unity的诞生:https://www.jianshu.com/p/550…...
未定义与 ‘double‘ 类型的输入参数相对应的函数 ‘Link‘
报错 检查对函数"Link"得调用中是否缺失参数或参数数据类型不正确。 未定义与"double"类型的输入参数相对应的函数"Link"。 问题描述 网上搜了搜一般说是toolbox没有下载导致的,相当于调用的包本地没有。 但是我看看了 Robotics…...
为什么Transformer模型中使用Layer Normalization(Layer Norm)而不是Batch Normalization(BN)
❤️觉得内容不错的话,欢迎点赞收藏加关注😊😊😊,后续会继续输入更多优质内容❤️ 👉有问题欢迎大家加关注私戳或者评论(包括但不限于NLP算法相关,linux学习相关,读研读博…...
Vite - 配置 - 文件路径别名的配置
为什么要配置别名 别名的配置,主要作用是为了缩短代码中的导入路径。例如有如下的项目目录: project-name| -- src| -- a| --b| --c| --d| --e| -- abc.png| -- index.html| -- main.js如果想在 main.js 文件中使用 abc.png ,则使用的路径是 ࿱…...
phpStorm Xdebug调试 加FireFox浏览器
步骤1: [Xdebug] zend_extension“D:\phpstudy_pro\Extensions\php\php5.4.45nts\ext\php_xdebug.dll” xdebug.collect_params1 xdebug.collect_return1 xdebug.remote_enableOn xdebug.remote_hostlocalhost xdebug.remote_port9001 xdebug.remote_handlerdbgp ;…...
多维时序 | MATLAB实现PSO-BiGRU-Attention粒子群优化双向门控循环单元融合注意力机制的多变量时间序列预测
多维时序 | MATLAB实现PSO-BiGRU-Attention粒子群优化双向门控循环单元融合注意力机制的多变量时间序列预测 目录 多维时序 | MATLAB实现PSO-BiGRU-Attention粒子群优化双向门控循环单元融合注意力机制的多变量时间序列预测预测效果基本介绍模型描述程序设计参考资料 预测效果 …...
linux配置固定ip(两种方法)
首先刚下载的vm,刚创建的虚拟机,肯定是需要配置ip的 其次以前我的每次都是设置自动ip,这样每次登录都会自动获取ip地址,并且每次的ip都不相同。 ~方法: 开机登陆后 1)Cd /etc/sysconfig/network-scripts 2)Vi ifcf…...
什么是缓存雪崩、击穿、穿透?
背景 数据一般是存储于数据库中,数据库中的数据都是存在磁盘上的,磁盘读写的速度相较于内存或者CPU中的寄存器来说是非常慢的了。 如果用户的请求都直接访问数据库的话,请求数量一上来,数据库很容易就崩溃了,所以为了…...
利用ngx_stream_return_module构建简易 TCP/UDP 响应网关
一、模块概述 ngx_stream_return_module 提供了一个极简的指令: return <value>;在收到客户端连接后,立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量(如 $time_iso8601、$remote_addr 等)&a…...
WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)
一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解,适合用作学习或写简历项目背景说明。 🧠 一、概念简介:Solidity 合约开发 Solidity 是一种专门为 以太坊(Ethereum)平台编写智能合约的高级编…...
uniapp中使用aixos 报错
问题: 在uniapp中使用aixos,运行后报如下错误: AxiosError: There is no suitable adapter to dispatch the request since : - adapter xhr is not supported by the environment - adapter http is not available in the build 解决方案&…...
使用Spring AI和MCP协议构建图片搜索服务
目录 使用Spring AI和MCP协议构建图片搜索服务 引言 技术栈概览 项目架构设计 架构图 服务端开发 1. 创建Spring Boot项目 2. 实现图片搜索工具 3. 配置传输模式 Stdio模式(本地调用) SSE模式(远程调用) 4. 注册工具提…...
无人机侦测与反制技术的进展与应用
国家电网无人机侦测与反制技术的进展与应用 引言 随着无人机(无人驾驶飞行器,UAV)技术的快速发展,其在商业、娱乐和军事领域的广泛应用带来了新的安全挑战。特别是对于关键基础设施如电力系统,无人机的“黑飞”&…...
MySQL 索引底层结构揭秘:B-Tree 与 B+Tree 的区别与应用
文章目录 一、背景知识:什么是 B-Tree 和 BTree? B-Tree(平衡多路查找树) BTree(B-Tree 的变种) 二、结构对比:一张图看懂 三、为什么 MySQL InnoDB 选择 BTree? 1. 范围查询更快 2…...
pikachu靶场通关笔记19 SQL注入02-字符型注入(GET)
目录 一、SQL注入 二、字符型SQL注入 三、字符型注入与数字型注入 四、源码分析 五、渗透实战 1、渗透准备 2、SQL注入探测 (1)输入单引号 (2)万能注入语句 3、获取回显列orderby 4、获取数据库名database 5、获取表名…...
嵌入式常见 CPU 架构
架构类型架构厂商芯片厂商典型芯片特点与应用场景PICRISC (8/16 位)MicrochipMicrochipPIC16F877A、PIC18F4550简化指令集,单周期执行;低功耗、CIP 独立外设;用于家电、小电机控制、安防面板等嵌入式场景8051CISC (8 位)Intel(原始…...
若依登录用户名和密码加密
/*** 获取公钥:前端用来密码加密* return*/GetMapping("/getPublicKey")public RSAUtil.RSAKeyPair getPublicKey() {return RSAUtil.rsaKeyPair();}新建RSAUti.Java package com.ruoyi.common.utils;import org.apache.commons.codec.binary.Base64; im…...
起重机起升机构的安全装置有哪些?
起重机起升机构的安全装置是保障吊装作业安全的关键部件,主要用于防止超载、失控、断绳等危险情况。以下是常见的安全装置及其功能和原理: 一、超载保护装置(核心安全装置) 1. 起重量限制器 功能:实时监测起升载荷&a…...
