当前位置: 首页 > 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;也就是思路…...

web vue 项目 Docker化部署

Web 项目 Docker 化部署详细教程 目录 Web 项目 Docker 化部署概述Dockerfile 详解 构建阶段生产阶段 构建和运行 Docker 镜像 1. Web 项目 Docker 化部署概述 Docker 化部署的主要步骤分为以下几个阶段&#xff1a; 构建阶段&#xff08;Build Stage&#xff09;&#xff1a…...

C++实现分布式网络通信框架RPC(3)--rpc调用端

目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中&#xff0c;我们已经大致实现了rpc服务端的各项功能代…...

Java 语言特性(面试系列1)

一、面向对象编程 1. 封装&#xff08;Encapsulation&#xff09; 定义&#xff1a;将数据&#xff08;属性&#xff09;和操作数据的方法绑定在一起&#xff0c;通过访问控制符&#xff08;private、protected、public&#xff09;隐藏内部实现细节。示例&#xff1a; public …...

反射获取方法和属性

Java反射获取方法 在Java中&#xff0c;反射&#xff08;Reflection&#xff09;是一种强大的机制&#xff0c;允许程序在运行时访问和操作类的内部属性和方法。通过反射&#xff0c;可以动态地创建对象、调用方法、改变属性值&#xff0c;这在很多Java框架中如Spring和Hiberna…...

【git】把本地更改提交远程新分支feature_g

创建并切换新分支 git checkout -b feature_g 添加并提交更改 git add . git commit -m “实现图片上传功能” 推送到远程 git push -u origin feature_g...

Docker 本地安装 mysql 数据库

Docker: Accelerated Container Application Development 下载对应操作系统版本的 docker &#xff1b;并安装。 基础操作不再赘述。 打开 macOS 终端&#xff0c;开始 docker 安装mysql之旅 第一步 docker search mysql 》〉docker search mysql NAME DE…...

【电力电子】基于STM32F103C8T6单片机双极性SPWM逆变(硬件篇)

本项目是基于 STM32F103C8T6 微控制器的 SPWM(正弦脉宽调制)电源模块,能够生成可调频率和幅值的正弦波交流电源输出。该项目适用于逆变器、UPS电源、变频器等应用场景。 供电电源 输入电压采集 上图为本设计的电源电路,图中 D1 为二极管, 其目的是防止正负极电源反接, …...

脑机新手指南(七):OpenBCI_GUI:从环境搭建到数据可视化(上)

一、OpenBCI_GUI 项目概述 &#xff08;一&#xff09;项目背景与目标 OpenBCI 是一个开源的脑电信号采集硬件平台&#xff0c;其配套的 OpenBCI_GUI 则是专为该硬件设计的图形化界面工具。对于研究人员、开发者和学生而言&#xff0c;首次接触 OpenBCI 设备时&#xff0c;往…...

python爬虫——气象数据爬取

一、导入库与全局配置 python 运行 import json import datetime import time import requests from sqlalchemy import create_engine import csv import pandas as pd作用&#xff1a; 引入数据解析、网络请求、时间处理、数据库操作等所需库。requests&#xff1a;发送 …...

​​企业大模型服务合规指南:深度解析备案与登记制度​​

伴随AI技术的爆炸式发展&#xff0c;尤其是大模型&#xff08;LLM&#xff09;在各行各业的深度应用和整合&#xff0c;企业利用AI技术提升效率、创新服务的步伐不断加快。无论是像DeepSeek这样的前沿技术提供者&#xff0c;还是积极拥抱AI转型的传统企业&#xff0c;在面向公众…...