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

详解线段树 ---更新查询

目录

一.问题引入

二.线段树

1.什么是线段树

2.线段树的举例

三.构建线段树

1.思路分析

2.代码实现

四.更新

1.思路分析

2.代码实现

五.查询

1.思路分析

2.代码实现


一.问题引入

有n个整数的数组,我们要 求解下标从left到right的元素之和为多少(query操作),然后还需要更新下标为index的值改为val(update操作),这个时候的时间复杂度为多少.

方法一:对于第一个问题(query)直接相加,这样的时间复杂度为O(n),第二个问题(update)的时间复杂度为O(1)

方法二:如果我们需要多次的query操作,我们是否有方法可以将降低时间复杂度?这个时候最好的办法就是把这n个整数的前缀和数组求解出来,每一次只需要prefix[right]-prefix[left-1]即可求解出来答案,这样的时间复杂度就降到了O(1),但是这个时候update操作的时间复杂度就升到了O(n),因为我们需要对前缀和数组index之后都进行修改.具体可以参考这篇博客看前缀和相关的内容:Java之前缀和算法_java前缀和算法_允歆辰丶的博客-CSDN博客

因此当我们采用无论哪一种方法,对于一种操作的时间复杂度可能很低,但是对另外一种操作的时间复杂度是很高的,因此是否可以有一种方法,可能将两种操作的时间复杂度平均一下,当然有,就是我们接下来要介绍的线段树,对于两种操作的时间复杂度都为O(log n);

二.线段树

1.什么是线段树

线段树是一种经典的数据结构,用于处理区间查询问题,例如区间求和区间最小值区间最大值等。它的基本思想是将区间递归地划分为若干个子区间,并将每个子区间的信息保存在一个节点中,从而形成一棵树形结构,即线段树。

线段树的每个节点都代表一个区间,如果该节点表示的区间与待查询的区间有交集,那么该节点保存的信息就可能对查询有用。因此,在查询时,只需要访问与待查询区间相交的节点即可,而不需要访问整棵树。

线段树通常使用数组来实现,其空间复杂度为 O(n),其中n是区间的长度。线段树的建树复杂度为 O(n),单次查询复杂度为 O(\log n)。

2.线段树的举例

我们对数组arr(如下图)构建一颗线段树(如下下图),此时叶子结点就是数组下标为index的值,他们的根结点为叶子结点的之和,一层层向上,根结点为整个数组的和36(也就是index为0到5的和)

三.构建线段树

1.思路分析

构建一颗线段树可以用数组来模拟树的实现,知道根结点下标(也就是tree数组的node),这个时候它的左子节点为:node_left = node * 2 + 1;右子节点为:node_right = node * 2 + 2;node左节点的对应arr数组的下标范围为[start,mid],node右节点的对应arr数组的下标范围为[mid,end],这个时候我们进行递归创建这个tree数组,我们可以知道递归要到叶子结点,对叶子结点的下标进行赋值,然后再一步步回溯向上对上一层的父节点进行赋值,最后完成对根结点的赋值,所以我们递归的出口为递归到叶子结点,也就是start==end,这个时候赋值 tree[node] = arr[start];

2.代码实现

    public static void buildTree(int[] arr, int[] tree, int node, int start, int end) {if (start == end) {tree[node] = arr[start];return;}int mid = (start + end) / 2;int node_left = node * 2 + 1;int node_right = node * 2 + 2;buildTree(arr, tree, node_left, start, mid);buildTree(arr, tree, node_right, mid + 1, end);tree[node] = tree[node_left] + tree[node_right];}

四.更新

1.思路分析

当我们需要对arr数组中的下标为index的元素进行数值的修改,这个时候也需要对线段树进行更新,例如将下标为3的数值修改为6,这个时候需要递归到下标范围为3的tree数组的下标,然后对值进行修改,然后一层层向上回溯对这半区的树值全部进行修改,我们只需要加上一个范围的判断,选择往左子树递归还是向右子树递归即可

2.代码实现

    public static void updateTree(int[] arr, int[] tree, int node, int start, int end, int index, int val) {if (start == end) {arr[index] = val;tree[node] = val;return;}int mid = (start + end) / 2;int node_left = node * 2 + 1;int node_right = node * 2 + 2;if (index >= start && index <= mid) {updateTree(arr, tree, node * 2 + 1, start, mid, index, val);} else {updateTree(arr, tree, node * 2 + 2, mid + 1, end, index, val);}tree[node] = tree[node_left] + tree[node_right];}

五.查询

1.思路分析

查询代码实现起来是有一定的复杂,首先我们可以先判断返回值为0的情况,也就是需要求和的范围不在当前树的根结点所在的范围内的,一共有两种情况:一种当start>right,一种当left>end,这个时候直接返回0.

 还有当出现如下图的情况时,直接返回当前结点的值,没必要继续向下递归,因为此时范围全部都符合了

 这个时候最后我们需要把左边的符合范围的和 加上 右边符合范围的和 ,最终的结果就是我们需要求解的范围.

2.代码实现

    /*** * @param arr  原数组* @param tree  构建的tree数组* @param node  根结点在tree数组的下标* @param start 原数组从start索引开始* @param end   原数组到end索引结束* @param left  求和从left索引开始* @param right  到right索引结束的和* @return*/public static int queryTree(int[] arr, int[] tree, int node, int start, int end, int left, int right) {if (right < start || end < left) {return 0;} else if (left <= start && right >= end) {return tree[node];}int mid = (start + end) / 2;int node_left = node * 2 + 1;int node_right = node * 2 + 2;int sum_left = queryTree(arr, tree, node_left, start, mid, left, right);int sum_right = queryTree(arr, tree, node_right, mid + 1, end, left, right);return sum_left + sum_right;}

 

相关文章:

详解线段树 ---更新查询

目录 一.问题引入 二.线段树 1.什么是线段树 2.线段树的举例 三.构建线段树 1.思路分析 2.代码实现 四.更新 1.思路分析 2.代码实现 五.查询 1.思路分析 2.代码实现 一.问题引入 有n个整数的数组,我们要 求解下标从left到right的元素之和为多少(query操作),然后还…...

【C语言进阶:刨根究底字符串函数】strncpy、strncat、strncmp函数

再前几篇的博客中大家可能发现了&#xff0c;strcpy&#xff0c;strcat&#xff0c;strcmp 这三个函数在使用时对源字符串没有长度限制&#xff0c;几乎是将源字符串的内容全部进行操作。在VS编译器中的这些函数显得不安全了&#xff0c;因此VS会提醒你在其后加上 _s &#x…...

计算机面试常见问答题目

英语口语 自我介绍 Hello, teachers. My name is Wang Xu. I come from Ningxia. I graduated from the School of Computer Science, Xi an Jiaotong University, majoring in Internet of Things. Next, I will introduce myself from four aspects. First of all, I studi…...

mac pro m1:安装dump文件内存分析工具——MAT

0. 引言 本文主要针对mac m1下安装Jprofiler进行讲解&#xff0c;安装核心步骤同样适用于其他系统 1. 安装 如果使用的是eclipse可以在插件中直接安装MAT&#xff0c;因为我使用的是idea开发&#xff0c;所以选择独立安装MAT工具 1、下载地址&#xff1a;https://www.eclip…...

并发基础之线程池(Thread Pool)

目录前言何为线程池线程池优势创建线程池方式直接实例化ThreadPoolExecutor类JUC Executors 创建线程池线程池挖掘Executors简单介绍ThreadPoolExecutor核心类ThreadPoolExecutor 类构造参数含义线程池运行规则线程设置数量结语前言 相信大家都知道当前的很多系统架构都要求高…...

【C语言进阶】内存函数

天生我材必有用&#xff0c;千金散尽还复来。 ——李白 目录 前言 一.memcpy函数 ​1.实现memcpy函数 2.模拟实现memcpy函数 二.memmove函数 1.实现memmove函数 2.模拟实现memmove函数 三.memcpy函数和memmove函数的关系 四.memcm…...

Java开发 - ELK初体验

前言 前面我们讲过消息队列&#xff0c;曾提到消息队列也具有保存消息日志的能力&#xff0c;今天要说的EL看也具备这个能力&#xff0c;不过还是要区分一下功能的。消息队列的日志主要指的是Redis的AOF&#xff0c;实际上只是可以利用了消息队列来保存&#xff0c;却并不是消…...

AI_Papers周刊:第六期

CV - 计算机视觉 | ML - 机器学习 | RL - 强化学习 | NLP 自然语言处理 2023.03.13—2023.03.19 文摘词云 Top Papers Subjects: cs.CL 1.UPRISE: Universal Prompt Retrieval for Improving Zero-Shot Evaluation 标题&#xff1a;UPRISE&#xff1a;改进零样本评估…...

JS运行环境、包管理、打包工具总结

&#x1f333;JS运行环境-node.js 运行环境就是代码解析和执行的程序&#xff0c;比如jvm等虚拟机&#xff0c;他们的主要工作就是根据设定的语法规则解析编译代码&#xff0c;然后运行代码。 js的语法规则遵循ES规范。 &#x1f341;node.js Node.Js官网 Node.js是一种基于Ch…...

day4网络编程(广播和组播)

1.广播 发送端&#xff08;类似于客户端&#xff09; 流程&#xff1a; 创建套接字 填充接收端&#xff08;服务器&#xff09;网络信息结构体 bind(非必须绑定) 设置允许广播 向接收端&#xff08;服务器&#xff09;发送数据 关闭套接字文件 #include <stdio.h> #in…...

Vue3 自动引入组件及函数、动态生成侧边栏路由

Vue3 自动引入组件及函数、动态生成侧边栏路由 1、安装依赖 npm install -D unplugin-auto-import unplugin-icons unplugin-vue-components插件使用说明 unplugin-auto-import 说明 —— 自动引入函数、组件 unplugin-vue-components 说明 —— 自动注册组件 unplugin-ic…...

人工智能交互系统界面设计

文章目录前言一、项目介绍二、项目准备三、项目实施1.导入相关库文件2.人脸信息验证功能3.语音交互与TCP数据通信4.数据信息可视化四、相关附件前言 在现代信息化时代&#xff0c;图形化用户界面&#xff08;Graphical User Interface, GUI&#xff09;已经成为各种软件应用和…...

蓝桥杯嵌入式第一课--创建工程

概述学习本节之前&#xff0c;必须要先安装好 keil5 以及 CubeMX 等软硬件环境&#xff0c;如果你已经安装完成&#xff0c;请告诉自己&#xff1a;考试现在开始&#xff01;从CubeMX开始CubeMX是创建工程模板的软件&#xff0c;也是我们比赛时第一个要进行操作的软件。一、选择…...

Java面向对象:接口的学习

本文介绍了Java中接口的基本语法, 什么是接口, java中的接口 语法规则, 接口的使用,接口的特性,如何实现多个接口,接口间的继承,以及抽象类和接口的区别 Java接口的学习一.接口的概念二.Java中的接口1.接口语法规则2.接口的使用3.接口的特性4.实现多个接口5.接口间的继承三.抽象…...

西瓜视频登录页面

题目 代码 <!DOCTYPE html> <html><head><meta charset"utf-8"><title>登录页面</title><style>td{width: 160px;height: 25px;}img{width: 20px;height: 20px;}.number, .password{background: rgba(0,0,0,.05);}.numbe…...

【springboot】常用快捷键:

Ctrl快捷键介绍Ctrl F在当前文件进行文本查找 &#xff08;必备&#xff09;Ctrl R在当前文件进行文本替换 &#xff08;必备&#xff09;Ctrl Z撤销 &#xff08;必备&#xff09;Ctrl Y删除光标所在行 或 删除选中的行 &#xff08;必备&#xff09;Ctrl X剪切光标所在行…...

宝塔控制面板常用Linux命令大全

宝塔面板是站长朋友们常见的一款服务器运维面板&#xff0c;可以通过 Web 端轻松管理服务器&#xff0c;提升运维效率。大家在服务器中安装宝塔面板会用到宝塔面板特定的脚本命令。今天这篇文章为大家整理汇总了宝塔面板常用Linux命令&#xff0c;这样方便大家收藏查找。 1、安…...

C语言实现单链表(超多配图,这下不得不学会单链表了)

目录 一&#xff1a;什么是链表&#xff1f; 二&#xff1a;创建源文件和头文件 (1)头文件 (2)源文件 三&#xff1a;实参和形参 四&#xff1a;一步步实现单向链表 &#xff08;1&#xff09;建立一个头指针并置空 &#xff08;2&#xff09;打印链表&#xff0c;便于…...

SQL编写优化技巧

一、底层原理 sql慢是因为没有走索引&#xff0c;因此需要添加索引然它走索引联合索引需要匹配最左匹配原则&#xff08;索引回表&#xff09;如果查询列超出索引的key&#xff0c; 会导致回表&#xff0c;回表数量多&#xff0c;则会走全表扫描 索引是分聚集索引、非聚集索引…...

【基础算法】单链表的OJ练习(6) # 复制带随机指针的链表 #

文章目录&#x1f347;前言&#x1f34e;复制带随机指针的链表&#x1f351;写在最后&#x1f347;前言 本章的链表OJ练习&#xff0c;是最后的也是最难的。对于本题&#xff0c;我们不仅要学会解题的思路&#xff0c;还要能够通过这个思路正确的写出代码&#xff0c;也就是思路…...

rknn优化教程(二)

文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK&#xff0c;开始写第二篇的内容了。这篇博客主要能写一下&#xff1a; 如何给一些三方库按照xmake方式进行封装&#xff0c;供调用如何按…...

解锁数据库简洁之道:FastAPI与SQLModel实战指南

在构建现代Web应用程序时&#xff0c;与数据库的交互无疑是核心环节。虽然传统的数据库操作方式&#xff08;如直接编写SQL语句与psycopg2交互&#xff09;赋予了我们精细的控制权&#xff0c;但在面对日益复杂的业务逻辑和快速迭代的需求时&#xff0c;这种方式的开发效率和可…...

为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?

在建筑行业&#xff0c;项目管理的重要性不言而喻。随着工程规模的扩大、技术复杂度的提升&#xff0c;传统的管理模式已经难以满足现代工程的需求。过去&#xff0c;许多企业依赖手工记录、口头沟通和分散的信息管理&#xff0c;导致效率低下、成本失控、风险频发。例如&#…...

css的定位(position)详解:相对定位 绝对定位 固定定位

在 CSS 中&#xff0c;元素的定位通过 position 属性控制&#xff0c;共有 5 种定位模式&#xff1a;static&#xff08;静态定位&#xff09;、relative&#xff08;相对定位&#xff09;、absolute&#xff08;绝对定位&#xff09;、fixed&#xff08;固定定位&#xff09;和…...

【论文阅读28】-CNN-BiLSTM-Attention-(2024)

本文把滑坡位移序列拆开、筛优质因子&#xff0c;再用 CNN-BiLSTM-Attention 来动态预测每个子序列&#xff0c;最后重构出总位移&#xff0c;预测效果超越传统模型。 文章目录 1 引言2 方法2.1 位移时间序列加性模型2.2 变分模态分解 (VMD) 具体步骤2.3.1 样本熵&#xff08;S…...

【Oracle】分区表

个人主页&#xff1a;Guiat 归属专栏&#xff1a;Oracle 文章目录 1. 分区表基础概述1.1 分区表的概念与优势1.2 分区类型概览1.3 分区表的工作原理 2. 范围分区 (RANGE Partitioning)2.1 基础范围分区2.1.1 按日期范围分区2.1.2 按数值范围分区 2.2 间隔分区 (INTERVAL Partit…...

LRU 缓存机制详解与实现(Java版) + 力扣解决

&#x1f4cc; LRU 缓存机制详解与实现&#xff08;Java版&#xff09; 一、&#x1f4d6; 问题背景 在日常开发中&#xff0c;我们经常会使用 缓存&#xff08;Cache&#xff09; 来提升性能。但由于内存有限&#xff0c;缓存不可能无限增长&#xff0c;于是需要策略决定&am…...

计算机基础知识解析:从应用到架构的全面拆解

目录 前言 1、 计算机的应用领域&#xff1a;无处不在的数字助手 2、 计算机的进化史&#xff1a;从算盘到量子计算 3、计算机的分类&#xff1a;不止 “台式机和笔记本” 4、计算机的组件&#xff1a;硬件与软件的协同 4.1 硬件&#xff1a;五大核心部件 4.2 软件&#…...

Python 高级应用10:在python 大型项目中 FastAPI 和 Django 的相互配合

无论是python&#xff0c;或者java 的大型项目中&#xff0c;都会涉及到 自身平台微服务之间的相互调用&#xff0c;以及和第三发平台的 接口对接&#xff0c;那在python 中是怎么实现的呢&#xff1f; 在 Python Web 开发中&#xff0c;FastAPI 和 Django 是两个重要但定位不…...

Python第七周作业

Python第七周作业 文章目录 Python第七周作业 1.使用open以只读模式打开文件data.txt&#xff0c;并逐行打印内容 2.使用pathlib模块获取当前脚本的绝对路径&#xff0c;并创建logs目录&#xff08;若不存在&#xff09; 3.递归遍历目录data&#xff0c;输出所有.csv文件的路径…...