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

【数据结构】线段树(点修区查)

数据结构-线段树(点修区查)


前置知识
  • 分治
  • 递归
  • 二叉树

思路

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

具体实现也很简单,如下:

  1. 建树( build \text{build} build
    从根节点向下遍历,叶节点自更新,非叶节点使用儿子节点更新( pushup \text{pushup} pushup
  2. 更新( update \text{update} update
    从根节点向下遍历,类似二分查找查找至叶结点,叶节点自更新,非叶节点使用儿子节点更新( pushup \text{pushup} pushup
  3. 查询( 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
    因为这个版本的线段树和树状数组差不多。。。

相关文章:

【数据结构】线段树(点修区查)

数据结构-线段树&#xff08;点修区查&#xff09; 前置知识 分治递归二叉树 思路 我们需要维护一个支持单点修改&#xff0c;区间查询的数据结构&#xff0c;并且要求在线&#xff0c;一般使用线段树解决。 线段树是一个二叉树形的数据结构。 线段树的思想很简单&#xff0c…...

Ansys Lumerical | 用于增强现实系统的表面浮雕光栅

在本示例中&#xff0c;我们使用 RCWA 求解器设计了一个斜面浮雕光栅 (SRG)&#xff0c;它将用于将光线耦合到单色增强现实 (AR) 系统的波导中。光栅的几何形状经过优化&#xff0c;可将正常入射光导入-1 光栅阶次。 然后我们将光栅特性导出为 Lumerical Sub-Wavelength Model …...

QT day3作业

1.思维导图 2、 完善对话框&#xff0c;点击登录对话框&#xff0c;如果账号和密码匹配&#xff0c;则弹出信息对话框&#xff0c;给出提示”登录成功“&#xff0c;提供一个Ok按钮&#xff0c;用户点击Ok后&#xff0c;关闭登录界面&#xff0c;跳转到其他界面 如果账号和密…...

【Ubuntu】设置永不息屏与安装 dconf-editor

方式一、GUI界面进行设置 No LSB modules are available. Distributor ID: Ubuntu Description: Ubuntu 20.04.6 LTS Release: 20.04 Codename: focal打开 Ubuntu 桌面环境的设置菜单。你可以通过点击屏幕右上角的系统菜单&#xff0c;然后选择设置。在设置菜单中&#xff0c;…...

gRPC 的原理 介绍带你从头了解gRPC

gRPC 的原理 什么是gRPC gRPC的官方介绍是&#xff1a;gRPC是一个现代的、高性能、开源的和语言无关的通用 RPC 框架&#xff0c;基于 HTTP2 协议设计&#xff0c;序列化使用PB(Protocol Buffer)&#xff0c;PB 是一种语言无关的高性能序列化框架&#xff0c;基于 HTTP2PB 保…...

Apriori算法

Apriori算法由R. Agrawal和R. Srikant于1994年在数据集中寻找布尔关联规则的频繁项集。该算法的名称是Apriori&#xff0c;因为它使用了频繁项集属性的先验知识。我们应用迭代方法或逐层搜索&#xff0c;其中k-频繁项集用于找到k1个项集。 为了提高频繁项集逐层生成的效率&…...

肖sir__linux讲解(2.1)

linux命令 cp 复制命令 a、cp 原文件名称 新文 件名称&#xff08;不存在的文件&#xff09; 案例&#xff1a;cp a k 截图&#xff1a; b.cp 原文件名称 原有文 件名称&#xff08;存在的文件&#xff09; 案例:cp a b 截图&#xff1a; c、cp 指定路径复制 格式&#xff…...

The ultimate UI kit and design system for Figma 组件库下载

Untitled UI 是世界上最大的 Figma UI 套件和设计系统。可以启动任何项目&#xff0c;为您节省数千小时&#xff0c;并祝您升级为专业设计师。 采用 100% 自动布局 5.0、变量、智能变体和 WCAG 可访问性精心制作。 900全局样式、变量&#xff1a;超级智能的全局颜色、排版和效…...

Selenium——利用input标签上传文件

Selenium利用input标签上传文件 完整流程 打开文件上传页面选择要上传的文件点击上传按钮确认文件上传成功介绍怎么方便的获取对应元素的Xpath或者Css 简单介绍 在使用Selenium进行浏览器自动化测试时&#xff0c;文件上传是一个常见的需求。而 标签就是实现文件上传功能的…...

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是一套新框架&#xff0c;因此并没有包含我们构建专业应用所需的所有工具。这意味着我们会需要求助于UIKit&#xff08;移动设备&#xff09;和AppKit&#xff08;Mac电脑&#xff09;等原…...

7.docker运行redis容器

1.准备redis的配置文件 从上一篇运行MySQL容器我们知道&#xff0c;需要给容器挂载数据卷&#xff0c;来持久化数据和配置&#xff0c;相应的redis也不例外。这里我们以redis6.0.8为例来实际说明下。 1.1 查找redis的配置文件redis.conf 下面这个网址有各种版本的配置文件供…...

unity教程

前言 伴随游戏行业的兴起&#xff0c;unity引擎的使用越来越普遍&#xff0c;本文章主要记录博主本人入门unity的相关记录大部分依赖siki学院进行整理。12 一、认识unity引擎&#xff1f; 1、Unity相关信息&#xff1a; Unity的诞生&#xff1a;https://www.jianshu.com/p/550…...

未定义与 ‘double‘ 类型的输入参数相对应的函数 ‘Link‘

报错 检查对函数"Link"得调用中是否缺失参数或参数数据类型不正确。 未定义与"double"类型的输入参数相对应的函数"Link"。 问题描述 网上搜了搜一般说是toolbox没有下载导致的&#xff0c;相当于调用的包本地没有。 但是我看看了 Robotics…...

为什么Transformer模型中使用Layer Normalization(Layer Norm)而不是Batch Normalization(BN)

❤️觉得内容不错的话&#xff0c;欢迎点赞收藏加关注&#x1f60a;&#x1f60a;&#x1f60a;&#xff0c;后续会继续输入更多优质内容❤️ &#x1f449;有问题欢迎大家加关注私戳或者评论&#xff08;包括但不限于NLP算法相关&#xff0c;linux学习相关&#xff0c;读研读博…...

Vite - 配置 - 文件路径别名的配置

为什么要配置别名 别名的配置&#xff0c;主要作用是为了缩短代码中的导入路径。例如有如下的项目目录&#xff1a; project-name| -- src| -- a| --b| --c| --d| --e| -- abc.png| -- index.html| -- main.js如果想在 main.js 文件中使用 abc.png ,则使用的路径是 &#xff1…...

phpStorm Xdebug调试 加FireFox浏览器

步骤1&#xff1a; [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&#xff0c;刚创建的虚拟机&#xff0c;肯定是需要配置ip的 其次以前我的每次都是设置自动ip&#xff0c;这样每次登录都会自动获取ip地址&#xff0c;并且每次的ip都不相同。 ~方法&#xff1a; 开机登陆后 1)Cd /etc/sysconfig/network-scripts 2)Vi ifcf…...

什么是缓存雪崩、击穿、穿透?

背景 数据一般是存储于数据库中&#xff0c;数据库中的数据都是存在磁盘上的&#xff0c;磁盘读写的速度相较于内存或者CPU中的寄存器来说是非常慢的了。 如果用户的请求都直接访问数据库的话&#xff0c;请求数量一上来&#xff0c;数据库很容易就崩溃了&#xff0c;所以为了…...

深度学习在微纳光子学中的应用

深度学习在微纳光子学中的主要应用方向 深度学习与微纳光子学的结合主要集中在以下几个方向&#xff1a; 逆向设计 通过神经网络快速预测微纳结构的光学响应&#xff0c;替代传统耗时的数值模拟方法。例如设计超表面、光子晶体等结构。 特征提取与优化 从复杂的光学数据中自…...

调用支付宝接口响应40004 SYSTEM_ERROR问题排查

在对接支付宝API的时候&#xff0c;遇到了一些问题&#xff0c;记录一下排查过程。 Body:{"datadigital_fincloud_generalsaas_face_certify_initialize_response":{"msg":"Business Failed","code":"40004","sub_msg…...

蓝牙 BLE 扫描面试题大全(2):进阶面试题与实战演练

前文覆盖了 BLE 扫描的基础概念与经典问题蓝牙 BLE 扫描面试题大全(1)&#xff1a;从基础到实战的深度解析-CSDN博客&#xff0c;但实际面试中&#xff0c;企业更关注候选人对复杂场景的应对能力&#xff08;如多设备并发扫描、低功耗与高发现率的平衡&#xff09;和前沿技术的…...

在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module

1、为什么要修改 CONNECT 报文&#xff1f; 多租户隔离&#xff1a;自动为接入设备追加租户前缀&#xff0c;后端按 ClientID 拆分队列。零代码鉴权&#xff1a;将入站用户名替换为 OAuth Access-Token&#xff0c;后端 Broker 统一校验。灰度发布&#xff1a;根据 IP/地理位写…...

【ROS】Nav2源码之nav2_behavior_tree-行为树节点列表

1、行为树节点分类 在 Nav2(Navigation2)的行为树框架中,行为树节点插件按照功能分为 Action(动作节点)、Condition(条件节点)、Control(控制节点) 和 Decorator(装饰节点) 四类。 1.1 动作节点 Action 执行具体的机器人操作或任务,直接与硬件、传感器或外部系统…...

Nginx server_name 配置说明

Nginx 是一个高性能的反向代理和负载均衡服务器&#xff0c;其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机&#xff08;Virtual Host&#xff09;。 1. 简介 Nginx 使用 server_name 指令来确定…...

TRS收益互换:跨境资本流动的金融创新工具与系统化解决方案

一、TRS收益互换的本质与业务逻辑 &#xff08;一&#xff09;概念解析 TRS&#xff08;Total Return Swap&#xff09;收益互换是一种金融衍生工具&#xff0c;指交易双方约定在未来一定期限内&#xff0c;基于特定资产或指数的表现进行现金流交换的协议。其核心特征包括&am…...

12.找到字符串中所有字母异位词

&#x1f9e0; 题目解析 题目描述&#xff1a; 给定两个字符串 s 和 p&#xff0c;找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义&#xff1a; 若两个字符串包含的字符种类和出现次数完全相同&#xff0c;顺序无所谓&#xff0c;则互为…...

uniapp中使用aixos 报错

问题&#xff1a; 在uniapp中使用aixos&#xff0c;运行后报如下错误&#xff1a; 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 解决方案&…...

(转)什么是DockerCompose?它有什么作用?

一、什么是DockerCompose? DockerCompose可以基于Compose文件帮我们快速的部署分布式应用&#xff0c;而无需手动一个个创建和运行容器。 Compose文件是一个文本文件&#xff0c;通过指令定义集群中的每个容器如何运行。 DockerCompose就是把DockerFile转换成指令去运行。 …...