当前位置: 首页 > 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;所以为了…...

【kafka】Golang实现分布式Masscan任务调度系统

要求&#xff1a; 输出两个程序&#xff0c;一个命令行程序&#xff08;命令行参数用flag&#xff09;和一个服务端程序。 命令行程序支持通过命令行参数配置下发IP或IP段、端口、扫描带宽&#xff0c;然后将消息推送到kafka里面。 服务端程序&#xff1a; 从kafka消费者接收…...

springboot 百货中心供应链管理系统小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;百货中心供应链管理系统被用户普遍使用&#xff0c;为方…...

条件运算符

C中的三目运算符&#xff08;也称条件运算符&#xff0c;英文&#xff1a;ternary operator&#xff09;是一种简洁的条件选择语句&#xff0c;语法如下&#xff1a; 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true&#xff0c;则整个表达式的结果为“表达式1”…...

Nuxt.js 中的路由配置详解

Nuxt.js 通过其内置的路由系统简化了应用的路由配置&#xff0c;使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...

工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配

AI3D视觉的工业赋能者 迁移科技成立于2017年&#xff0c;作为行业领先的3D工业相机及视觉系统供应商&#xff0c;累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成&#xff0c;通过稳定、易用、高回报的AI3D视觉系统&#xff0c;为汽车、新能源、金属制造等行…...

大学生职业发展与就业创业指导教学评价

这里是引用 作为软工2203/2204班的学生&#xff0c;我们非常感谢您在《大学生职业发展与就业创业指导》课程中的悉心教导。这门课程对我们即将面临实习和就业的工科学生来说至关重要&#xff0c;而您认真负责的教学态度&#xff0c;让课程的每一部分都充满了实用价值。 尤其让我…...

docker 部署发现spring.profiles.active 问题

报错&#xff1a; org.springframework.boot.context.config.InvalidConfigDataPropertyException: Property spring.profiles.active imported from location class path resource [application-test.yml] is invalid in a profile specific resource [origin: class path re…...

LLMs 系列实操科普(1)

写在前面&#xff1a; 本期内容我们继续 Andrej Karpathy 的《How I use LLMs》讲座内容&#xff0c;原视频时长 ~130 分钟&#xff0c;以实操演示主流的一些 LLMs 的使用&#xff0c;由于涉及到实操&#xff0c;实际上并不适合以文字整理&#xff0c;但还是决定尽量整理一份笔…...

【Linux手册】探秘系统世界:从用户交互到硬件底层的全链路工作之旅

目录 前言 操作系统与驱动程序 是什么&#xff0c;为什么 怎么做 system call 用户操作接口 总结 前言 日常生活中&#xff0c;我们在使用电子设备时&#xff0c;我们所输入执行的每一条指令最终大多都会作用到硬件上&#xff0c;比如下载一款软件最终会下载到硬盘上&am…...

Ubuntu系统复制(U盘-电脑硬盘)

所需环境 电脑自带硬盘&#xff1a;1块 (1T) U盘1&#xff1a;Ubuntu系统引导盘&#xff08;用于“U盘2”复制到“电脑自带硬盘”&#xff09; U盘2&#xff1a;Ubuntu系统盘&#xff08;1T&#xff0c;用于被复制&#xff09; &#xff01;&#xff01;&#xff01;建议“电脑…...