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

数据结构之线段树

线段树

线段树(Segment Tree)是一种高效的数据结构,广泛应用于计算机科学和算法中,特别是在处理区间查询和更新问题时表现出色。以下是对线段树的详细解释:

一、基本概念

线段树是一种二叉搜索树,是算法竞赛中常用的用来维护 区间信息 的数据结构。线段树可以在 O(logn) 的时间复杂度内实现单点修改、区间修改、区间查询(区间求和,求区间最大值,求区间最小值)等操作。

原理其实是分治思想。它将整个区间划分成一些单元区间,具有对数级别的高度,从而保证了高效的查询和更新操作。

二、基本结构

  • 根结点:代表整个区间。
  • 内部结点:每个内部结点都代表一个区间,并将其划分为左右两个子区间,分别由左孩子和右孩子表示。
  • 叶结点:代表单元区间,每个叶结点对应原始数据中的一个元素。

对于线段树中的每一个非叶子节点[a,b],它的左儿子表示的区间为[a,(a+b)/2],右儿子表示的区间为[(a+b)/2+1,b]。

三、示例应用

假设有一个长度为N的数组a,需要频繁地查询任意区间[l,r]的最小值和以及更新数组中的某个元素。使用线段树可以高效地解决这些问题。以下是一个简单的线段树实现示例(以Python代码表示):

class SegmentTree:  def __init__(self, nums):  self.nums = nums  self.n = len(nums)  # 初始化线段树,大小为4倍的原数组长度,因为线段树是完全二叉树  self.tree = [float('inf')] * (4 * self.n)  self.build_tree(0, 0, self.n - 1)  def build_tree(self, tree_index, l, r):  # 如果到达了叶节点  if l == r:  self.tree[tree_index] = self.nums[l]  return  # 计算左右子节点的索引  left_child = 2 * tree_index + 1  right_child = 2 * tree_index + 2  # 递归构建左右子树  mid = (l + r) // 2  self.build_tree(left_child, l, mid)  self.build_tree(right_child, mid + 1, r)  # 当前节点的值是其左右子节点值的最小值  self.tree[tree_index] = min(self.tree[left_child], self.tree[right_child])  def query(self, l, r):  return self.query_tree(0, 0, self.n - 1, l, r)  def query_tree(self, tree_index, seg_l, seg_r, query_l, query_r):  # 如果查询区间完全包含了当前线段树节点代表的区间  if query_l <= seg_l and seg_r <= query_r:  return self.tree[tree_index]  # 如果查询区间与当前线段树节点代表的区间没有交集  if query_l > seg_r or query_r < seg_l:  return float('inf')  # 计算左右子节点的索引  left_child = 2 * tree_index + 1  right_child = 2 * tree_index + 2  # 递归查询左右子树,并取最小值  mid = (seg_l + seg_r) // 2  left_min = self.query_tree(left_child, seg_l, mid, query_l, query_r)  right_min = self.query_tree(right_child, mid + 1, seg_r, query_l, query_r)  return min(left_min, right_min)  def update(self, index, value):  self.update_tree(0, 0, self.n - 1, index, value)  def update_tree(self, tree_index, seg_l, seg_r, index, value):  # 如果到达了叶节点  if seg_l == seg_r:  self.nums[index] = value  self.tree[tree_index] = value  return  # 计算左右子节点的索引  left_child = 2 * tree_index + 1  right_child = 2 * tree_index + 2  # 递归更新左右子树  mid = (seg_l + seg_r) // 2  if index <= mid:  self.update_tree(left_child, seg_l, mid, index, value)  else:  self.update_tree(right_child, mid + 1, seg_r, index, value)  # 当前节点的值是其左右子节点值的最小值  self.tree[tree_index] = min(self.tree[left_child], self.tree[right_child])  # 示例用法  
nums = [1, 3, 2, 7, 9, 11]  
seg_tree = SegmentTree(nums)  # 查询区间[1, 3]的最小值  
print(seg_tree.query(1, 3))  # 输出: 2  # 更新索引2处的值为0  
seg_tree.update(2, 0)  # 再次查询区间[1, 3]的最小值  
print(seg_tree.query(1, 3))  # 输出: 0

相关文章:

数据结构之线段树

线段树 线段树&#xff08;Segment Tree&#xff09;是一种高效的数据结构&#xff0c;广泛应用于计算机科学和算法中&#xff0c;特别是在处理区间查询和更新问题时表现出色。以下是对线段树的详细解释&#xff1a; 一、基本概念 线段树是一种二叉搜索树&#xff0c;是算法竞…...

vue 快速入门

文章目录 一、插值表达式 {{}}二、Vue 指令2.1 v-text 和 v-html&#xff1a;2.2 v-if 和 v-show&#xff1a;2.3 v-on&#xff1a;2.4 v-bind 和 v-model&#xff1a;2.5 v-for&#xff1a; 三、生命周期四、Vue 组件库 Element五、Vue 路由 本文章适用于后端人员&#xff0c;…...

iframe视频宽度高度自适应( pc+移动都可以用,jq写法 )

注意&#xff1a;要引入jquery 可以直接使用弹框播放iframe 一、创建 index.html <!DOCTYPE html> <html><head><meta charset"utf-8"><title></title><style>.modal {/* 默认隐藏 */display: none;position: fixed;z-i…...

Observability:OpenTelemetry Elastic 分发简介

作者&#xff1a;来自 Elastic Alexander Wert•Miguel Luna•Bahubali Shetti Elastic 自豪地推出了 Elastic Distributions of OpenTelemetry (EDOT)&#xff0c;其中包含 Elastic 版本的 OpenTelemetry Collector 和多种语言 SDK&#xff0c;如 Python、Java、.NET 和 NodeJ…...

golang的RSA加密解密

参考&#xff1a;https://blog.csdn.net/lady_killer9/article/details/118026802 1.加密解密工具类PasswordUtil.go package utilimport ("crypto/rand""crypto/rsa""crypto/x509""encoding/pem""fmt""log"&qu…...

深度学习-梯度消失/爆炸产生的原因、解决方法

在深度学习模型中&#xff0c;梯度消失和梯度爆炸现象是限制深层神经网络有效训练的主要问题之一&#xff0c;这两个现象从本质上来说是由链式求导过程中梯度的缩小或增大引起的。特别是在深层网络中&#xff0c;若初始梯度在反向传播过程中逐层被放大或缩小&#xff0c;最后导…...

MVC(Model-View-Controller)模式概述

MVC&#xff08;Model-View-Controller&#xff09;是一种设计模式&#xff0c;最初由 Trygve Reenskaug 在 1970 年代提出&#xff0c;并在 Smalltalk 编程环境中得到了广泛应用。MVC 模式旨在实现用户界面和业务逻辑的分离&#xff0c;以增强应用程序的可维护性、可扩展性和复…...

数据结构 —— 红黑树

目录 1. 初识红黑树 1.1 红黑树的概念 1.2 红⿊树的规则 1.3 红黑树如何确保最长路径不超过最短路径的2倍 1.4 红黑树的效率:O(logN) 2. 红黑树的实现 2.1 红黑树的基础结构框架 2.2 红黑树的插⼊ 2.2.1 情况1&#xff1a;变色 2.2.2 情况2&#xff1a;单旋变色 2.2…...

《功能高分子学报》

《功能高分子学报》 中国标准连续出版物号:CN 31-1633/O6&#xff0c;国际标准连续出版物号&#xff1a;ISSN 1008-9357&#xff0c;邮发代号&#xff1a;4-629&#xff0c;刊期&#xff1a;双月刊。 《功能高分子学报》主要刊登功能高分子和其他高分子领域具有创新意义的学术…...

Linux特种文件系统--tmpfs文件系统

tmpfs类似于RamDisk&#xff08;只能使用物理内存&#xff09;&#xff0c;使用虚拟内存&#xff08;简称VM&#xff09;子系统的页面存储文件。tmpfs完全依赖VM&#xff0c;遵循子系统的整体调度策略。说白了tmpfs跟普通进程差不多&#xff0c;使用的都是某种形式的虚拟内存&a…...

《基于STMF103的FreeRTOS内核移植》

目录 1.FreeRTOS资料下载与出处 1.1官网下载&#xff0c;网址&#xff1a;www.freertos.org 1.2在正点原子官网&#xff0c;任意STM32F1的开发板资料A盘里&#xff0c; 2.FreeRTOS移植重要文件讲解 2.1 FreeRTOS与FreeRTOS-Plus文件夹 2.2 Demo、Lincence、Source ●Demo文件…...

一七二、Vue3性能优化方式

Vue 3 的性能优化相较于 Vue 2 有了显著提升&#xff0c;利用新特性和改进方法可以更高效地构建和优化应用。以下是 Vue 3 的常见性能优化方法及示例。 1. 使用组合式 API (Composition API) Vue 3 引入的组合式 API&#xff0c;通过逻辑拆分和复用来实现更高效的代码组织和性…...

软件测试--BUG篇

博主主页: 码农派大星. 数据结构专栏:Java数据结构 数据库专栏:MySQL数据库 JavaEE专栏:JavaEE 软件测试专栏:软件测试 关注博主带你了解更多知识 目录 1. 软件测试的⽣命周期 2. BUG 1. BUG 的概念 2. 描述bug的要素 3.bug级别 4.bug的⽣命周期 5 与开发产⽣争执怎…...

Scikit-learn和Keras简介

一&#xff0c;Scikit-learn是一个开源的机器学习库&#xff0c;用于Python编程语言。它建立在NumPy、SciPy和matplotlib这些科学计算库之上&#xff0c;提供了简单有效的数据挖掘和数据分析工具。Scikit-learn库包含了许多用于分类、回归、聚类和降维的算法&#xff0c;包括支…...

python在word的页脚插入页码

1、插入简易页码 import win32com.client as win32 from win32com.client import constants import osdoc_app win32.gencache.EnsureDispatch(Word.Application)#打开word应用程序 doc_app.Visible Truedoc doc_app.Documents.Add() footer doc.Sections(1).Footers(cons…...

Java面试题十四

一、Java中的JNI&#xff08;Java Native Interface&#xff09;是什么&#xff1f;它有什么用途&#xff1f; Java中的JNI&#xff08;Java Native Interface&#xff09;是Java提供的一种编程框架&#xff0c;它允许Java代码与本地&#xff08;Native&#xff09;代码&#x…...

yarn : 无法加载文件,未对文件 进行数字签名。无法在当前系统上运行该脚本。

执行这个命令时报错&#xff1a;yarn --registryhttps://registry.npm.taobao.org yarn : 无法加载文件 C:\Users\Administrator\AppData\Roaming\npm\yarn.ps1。未对文件 C:\Users\Administ rator\AppData\Roaming\npm\yarn.ps1 进行数字签名。无法在当前系统上运行该脚本。有…...

Hadoop——HDFS

什么是HDFS HDFS&#xff08;Hadoop Distributed File System&#xff09;是Apache Hadoop的核心组件之一&#xff0c;是一个分布式文件系统&#xff0c;专门设计用于在大规模集群上存储和管理海量数据。它的设计目标是提供高吞吐量的数据访问和容错能力&#xff0c;以支持大数…...

计算机的一些基础知识

文章目录 编程语言 程序 所谓程序&#xff0c;就是 一组指令 以及 这组指令要处理的数据。狭义上来说&#xff0c;程序对我们来说&#xff0c;通常表现为一组文件。 程序 指令 指令要处理的数据。 编程语言发展 机器语言&#xff1a;0、1 二进制构成汇编语言&#xff1a;…...

学习RocketMQ(记录了个人艰难学习RocketMQ的笔记)

一、部署单点RocketMQ Docker 部署 RocketMQ (图文并茂超详细)_docker 部署rocketmq-CSDN博客 这个博主讲的很好&#xff0c;可食用&#xff0c;替大家实践了一遍 二、原理篇 为什么使用RocketMQ&#xff1a; 为什么选择RocketMQ | RocketMQ 关于一些原理&#xff0c;感觉…...

SpringBoot-17-MyBatis动态SQL标签之常用标签

文章目录 1 代码1.1 实体User.java1.2 接口UserMapper.java1.3 映射UserMapper.xml1.3.1 标签if1.3.2 标签if和where1.3.3 标签choose和when和otherwise1.4 UserController.java2 常用动态SQL标签2.1 标签set2.1.1 UserMapper.java2.1.2 UserMapper.xml2.1.3 UserController.ja…...

日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻

在如今就业市场竞争日益激烈的背景下&#xff0c;越来越多的求职者将目光投向了日本及中日双语岗位。但是&#xff0c;一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧&#xff1f;面对生疏的日语交流环境&#xff0c;即便提前恶补了…...

使用VSCode开发Django指南

使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架&#xff0c;专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用&#xff0c;其中包含三个使用通用基本模板的页面。在此…...

如何在看板中体现优先级变化

在看板中有效体现优先级变化的关键措施包括&#xff1a;采用颜色或标签标识优先级、设置任务排序规则、使用独立的优先级列或泳道、结合自动化规则同步优先级变化、建立定期的优先级审查流程。其中&#xff0c;设置任务排序规则尤其重要&#xff0c;因为它让看板视觉上直观地体…...

线程同步:确保多线程程序的安全与高效!

全文目录&#xff1a; 开篇语前序前言第一部分&#xff1a;线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分&#xff1a;synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分&#xff…...

电脑插入多块移动硬盘后经常出现卡顿和蓝屏

当电脑在插入多块移动硬盘后频繁出现卡顿和蓝屏问题时&#xff0c;可能涉及硬件资源冲突、驱动兼容性、供电不足或系统设置等多方面原因。以下是逐步排查和解决方案&#xff1a; 1. 检查电源供电问题 问题原因&#xff1a;多块移动硬盘同时运行可能导致USB接口供电不足&#x…...

高危文件识别的常用算法:原理、应用与企业场景

高危文件识别的常用算法&#xff1a;原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件&#xff0c;如包含恶意代码、敏感数据或欺诈内容的文档&#xff0c;在企业协同办公环境中&#xff08;如Teams、Google Workspace&#xff09;尤为重要。结合大模型技术&…...

C# 类和继承(抽象类)

抽象类 抽象类是指设计为被继承的类。抽象类只能被用作其他类的基类。 不能创建抽象类的实例。抽象类使用abstract修饰符声明。 抽象类可以包含抽象成员或普通的非抽象成员。抽象类的成员可以是抽象成员和普通带 实现的成员的任意组合。抽象类自己可以派生自另一个抽象类。例…...

【决胜公务员考试】求职OMG——见面课测验1

2025最新版&#xff01;&#xff01;&#xff01;6.8截至答题&#xff0c;大家注意呀&#xff01; 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:&#xff08; B &#xff09; A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...

【OSG学习笔记】Day 16: 骨骼动画与蒙皮(osgAnimation)

骨骼动画基础 骨骼动画是 3D 计算机图形中常用的技术&#xff0c;它通过以下两个主要组件实现角色动画。 骨骼系统 (Skeleton)&#xff1a;由层级结构的骨头组成&#xff0c;类似于人体骨骼蒙皮 (Mesh Skinning)&#xff1a;将模型网格顶点绑定到骨骼上&#xff0c;使骨骼移动…...