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

教你搞懂线段树,从基础到提高

秋名山码民的主页
🎉欢迎关注🔎点赞👍收藏⭐️留言📝
🙏作者水平有限,如发现错误,还请私信或者评论区留言!

目录

  • 前言
  • 线段树逻辑概念
    • 线段树的俩个重要用处
  • 代码实现线段树
  • 题目巩固
  • 最后


前言

线段树算是比较难的一个数据结构,当时我高中提高组就没学懂,细数我学线段树也学了4遍,最早学的时候一脸懵逼,最近在刷题中发现其在蓝桥杯中也有考察,就寻思写一篇博客来巩固。

什么是线段树,线段树有什么用,线段树怎么写,能不能背过???

我认为对于打比赛的各位来说,线段树和前缀和一样,不能算做算法,它更多的是一种工具,一种时间复杂度为O(logn)的单点修改,区间查询的工具

线段树逻辑概念

给定一个1~7的区间我们来维护它,将其转换为一个二叉树(线段树本身就是一个二叉树

  1. 最上面的根的权值,为28,1~7的和
  2. 二叉树开分,左边为1~4的和为10,右边为5 ~ 6的和为21
  3. 1~4在开分,左边为3,右边为7 ,5 ~6开分,左边为14,右边为7
  4. 同上,直到不能再分

L,R:
在这里插入图片描述

class node{int l,r;int sum;
}

在这里插入图片描述

线段树的俩个重要用处

1. 单点修改

如上图我们将5变成8,其中要修改的为1~ 7,5~ 7,5~ 6,5,

2. 区间查询

如上图我们计算2 ~ 5区间,如果完全包含某个区间,则退出,否则进行递归,用黄圈表示需要递归的区间

  1. 1~7区间,递归左边,1 ~4区间,发现还没有被完全包含,进行左右俩边都递归,1 ~2,3 ~4,此刻,3 ~4完全包含,不进行递归,继续递归1~ 2,2被完全包含
  2. 5~ 7区间,同上,进行递归
  3. 进行回溯区间,只算完全包含的区间,2+7+8 = 17

总结:
如果这个区间被完全包括在目标区间里面,直接返回这个区间的值
如果这个区间的左儿子和目标区间有交集,那么搜索左儿子
如果这个区间的右儿子和目标区间有交集,那么搜索右儿子

时间复杂度均为O(logn)

代码实现线段树

上面我们说线段树的俩个重要的用法,思考一下大概需要几个函数能实现?

  1. pushup:用子节点信息更新当前节点信息
  2. build:在一段区间上初始化线段树
  3. modify:修改
  4. query:查询

动态求连续区间和
在这里插入图片描述

import java.io.*;/*** @Author 秋名山码神* @Date 2023/2/9* @Description*/
public class 动态求连续区间和 {static int n, k;static int[] a = new int[100100];static Node[] tr = new Node[400400];static class Node{int l, r, sum;Node(int l, int r, int sum) {this.l = l;this.r = r;this.sum = sum;}}public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));String[] cd = br.readLine().split(" ");n = Integer.parseInt(cd[0]);k = Integer.parseInt(cd[1]);String[] line = br.readLine().split(" ");for (int i=1;i<=n;i++)a[i] = Integer.parseInt(line[i-1]);build(1, 1, n);while (k-- > 0) {String[] li = br.readLine().split(" ");int k = Integer.parseInt(li[0]), l = Integer.parseInt(li[1]), r = Integer.parseInt(li[2]);if(k == 0) {bw.write(String.valueOf(query(1, l, r)));bw.write("\n");} elsemodify(1, l, r);}bw.flush();}static void pushUp(int u) {tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;}static void build(int u, int l, int r) {if(l == r) tr[u] = new Node(l , r, a[l]);else {tr[u] = new Node(l ,r, 0);int mid = l + r >> 1;build(u << 1, l, mid); build(u << 1 | 1, mid + 1, r);pushUp(u);}}static int query(int u, int l, int r) {if(tr[u].l >= l && tr[u].r <= r) return tr[u].sum;int mid = tr[u].l + tr[u].r >> 1, sum = 0;if(l <= mid) sum += query(u << 1, l, r);if(r > mid) sum += query(u << 1 | 1, l , r);return sum;}static void modify(int u, int x, int v) {if(tr[u].l == tr[u].r) tr[u].sum += v;else {int mid = tr[u].l + tr[u].r >> 1;if(x <= mid) modify(u << 1, x , v);else modify(u << 1 | 1, x, v);pushUp(u);}}
}

题目巩固

区间和的个数

在这里插入图片描述

class Solution {public int countRangeSum(int[] nums, int lower, int upper) {int count = 0;int length = nums.length;long[] sums = new long[length + 1];for (int i = 0; i < length; i++) {sums[i + 1] = sums[i] + nums[i];}Set<Long> set = new HashSet<Long>();for (int i = 0; i <= length; i++) {long sum = sums[i];set.add(sum);set.add(sum - upper);set.add(sum - lower);}List<Long> sumsList = new ArrayList<Long>(set);Collections.sort(sumsList);Map<Long, Integer> ranks = new HashMap<Long, Integer>();int size = sumsList.size();for (int i = 0; i < size; i++) {ranks.put(sumsList.get(i), i);}SegmentTree st = new SegmentTree(size);for (int i = 0; i <= length; i++) {long sum = sums[i];int rank = ranks.get(sum);long minSum = sum - upper, maxSum = sum - lower;int start = ranks.get(minSum), end = ranks.get(maxSum);count += st.getCount(start, end);st.add(rank);}return count;}
}class SegmentTree {int length;int[] tree;public SegmentTree(int length) {this.length = length;this.tree = new int[length * 4];}public int getCount(int start, int end) {return getCount(start, end, 0, 0, length - 1);}public void add(int rank) {add(rank, 0, 0, length - 1);}private int getCount(int rangeStart, int rangeEnd, int index, int treeStart, int treeEnd) {if (rangeStart > rangeEnd) {return 0;}if (rangeStart == treeStart && rangeEnd == treeEnd) {return tree[index];}int mid = treeStart + (treeEnd - treeStart) / 2;if (rangeEnd <= mid) {return getCount(rangeStart, rangeEnd, index * 2 + 1, treeStart, mid);} else if (rangeStart > mid) {return getCount(rangeStart, rangeEnd, index * 2 + 2, mid + 1, treeEnd);} else {return getCount(rangeStart, mid, index * 2 + 1, treeStart, mid) + getCount(mid + 1, rangeEnd, index * 2 + 2, mid + 1, treeEnd);}}private void add(int rank, int index, int start, int end) {if (start == end) {tree[index]++;return;}int mid = start + (end - start) / 2;if (rank <= mid) {add(rank, index * 2 + 1, start, mid);} else {add(rank, index * 2 + 2, mid + 1, end);}tree[index] = tree[index * 2 + 1] + tree[index * 2 + 2];}
}

最后

看在博主这么努力,熬夜肝的情况下,给个免费的三连吧!
请添加图片描述

相关文章:

教你搞懂线段树,从基础到提高

秋名山码民的主页 &#x1f389;欢迎关注&#x1f50e;点赞&#x1f44d;收藏⭐️留言&#x1f4dd; &#x1f64f;作者水平有限&#xff0c;如发现错误&#xff0c;还请私信或者评论区留言&#xff01; 目录前言线段树逻辑概念线段树的俩个重要用处代码实现线段树题目巩固最后…...

C语言进阶——自定义类型:结构体

&#x1f307;个人主页&#xff1a;_麦麦_ &#x1f4da;今日名言&#xff1a;生活不可能像你想象的那么好&#xff0c;也不会像你想象的那么糟。——莫泊桑《羊脂球》 目录 一、前言 二、正文 1结构体 1.1结构体的基础知识 1.2结构的声明 1.3特殊的声明 1.4结构体变量的…...

SpringSecurity学习笔记01

目录 一、课程介绍 二、框架概述 三、入门案例 四、基本原理&#xff08;过滤器链&#xff09; 五、基本原理&#xff08;过滤器加载过程&#xff09; 六、基本原理&#xff08;两个重要的接口) 七、web权限方案-用户认证&#xff08;设置用户名密码上&#xff09; 八、…...

Python语言零基础入门教程(十一)

Python 列表(List) 序列是Python中最基本的数据结构。序列中的每个元素都分配一个数字 - 它的位置&#xff0c;或索引&#xff0c;第一个索引是0&#xff0c;第二个索引是1&#xff0c;依此类推。 Python有6个序列的内置类型&#xff0c;但最常见的是列表和元组。 序列都可以…...

现货白银基础知识

任何活动&#xff0c;任何项目&#xff0c;任何工作都离不开基础知识&#xff0c;这是肯定的。万丈高楼平地起&#xff0c;要想要简称百层高楼&#xff0c;首先得把低级打好&#xff01;现货白银投资也是一样的道理&#xff0c;现在我们就来一起聊聊现货白银基础知识的问题&…...

数据库原理及应用基础知识点

数据库原理基础知识点大全数据库原理及应用1、数据库系统概述1.1 基本概念1.2 数据模型1.3 数据库系统的结构2、实体 -- 联系模型2.1 基本概念2.2 实体-联系图2.3 弱实体集3、关系数据模型3.1 关系数据库的结构3.2 从ER模型到关系模型3.3 关系操作、完整性约束、关系代数4、关系…...

【数据结构】栈(stack)

写在前面本篇文章开始讲解栈的有关知识&#xff0c;其实把顺序表和链表学好&#xff0c;那么这一章便不在话下&#xff0c;栈实际上就是顺序表或链表的一些特殊情况。用顺序表实现的栈叫做顺序栈用链表实现的栈叫做链栈文章的内容分为几个部分&#xff0c;希望读者能快速了解文…...

初识shell

文章目录一、shell基本知识1.1为什么学习和使用Shell编程1.2 什么是Shell1.2.1 shell的起源1.2.2 shell的功能1.3 shell的分类1.4 作为程序设计的语言——shell1.5 如何学好shell1.6 shell脚本的基本元素1.7 shell脚本编写规范1.8shell脚本的执行方式1.9 执行脚本的方法1.10 sh…...

程序员如何编写好开发技术文档 如何编写优质的API文档工作

编写技术文档&#xff0c;是令众多开发者望而生畏的任务之一。它本身是一件费时费力才能做好的工作。可是大多数时候&#xff0c;人们却总是想抄抄捷径&#xff0c;这样做的结果往往非常令人遗憾的&#xff0c;因为优质的技术文档是决定你的项目是否引人关注的重要因素。无论开…...

二级C语言操作例题(四十)

一、程序填空题 在此程序中&#xff0c;函数fun的功能是&#xff1a;在形参s所指字符串中寻找与参数c相同的字符&#xff0c;并在其后插入一个与之相同的字符&#xff0c;若找不到相同的字符则不做任何处理。 例如&#xff0c;若s所指字符串”baacda”&#xff0c;中c的字符为…...

vue-router 源码解析(二)-创建路由匹配对象

文章目录基本使用导语createRouterMatcher 创建匹配路由记录addRoute 递归添加matchercreateRouteRecordMatcher 创建matchertokenizePath 解析pathtokensToParser 记录打分insertMatcher 将matcher排序总结基本使用 const routes [{path:"/",component: Demo2,nam…...

分布式新闻项目实战 - 10.Long类型精度丢失问题

怒发冲冠&#xff0c;凭阑处、潇潇雨歇。抬望眼&#xff0c;仰天长啸&#xff0c;壮怀激烈。三十功名尘与土&#xff0c;八千里路云和月。莫等闲、白了少年头&#xff0c;空悲切。 靖康耻&#xff0c;犹未雪。臣子恨&#xff0c;何时灭。驾长车&#xff0c;踏破贺兰山缺。壮志饥…...

如何将本地jar包安装到maven仓库

mvn install:install-file:主要是将本地自定义jar安装到maven仓库&#xff0c;然后在pom中可以直接通过dependency的方式来引用。 此命令有如参数&#xff1a; 命令说明-DgroupId自定义groupId设置groupId 名-DartifactId自定义artifactId设置该包artifactId名-Dversion自定义…...

C++:map和set的认识和简单使用/关联式容器

关联式容器 关联式容器即是用来存储数据的&#xff0c;并且存储的是<Key&#xff0c;Value>结构的键值对&#xff0c;在数据检索时效率比序列式容器高。 序列式容器也就是vector、list、queue等容器&#xff0c;因为其底层为线性序列的数据结构&#xff0c;里面存储的是…...

网络工程师一定要学会的知识点:OSPF,今天给大家详细介绍

1. OSPF 概念OSPF&#xff08;Open Shortest Path First 开放式最短路径优先&#xff09;是一种动态路由协议&#xff0c;属于内部网关协议(Interior Gateway Protocol,简称 IGP)&#xff0c;是基于链路状态算法的路由协议。2. OSPF 的运行原理&#xff08;1&#xff09;OSPF 的…...

企业管理的三大基石及其关系

企业管理的三大基石三大基石是什么三大基石的关系制度&#xff1a;管理&#xff1a;文化&#xff1a;三大基石是什么 一个企业&#xff0c;不管它是属于哪种类型&#xff0c;影响员工行为的都有三种力量——制度、管理和文化&#xff0c;这是管理的三大基石。 三大基石的关系 …...

6个月软件测试培训出来后的感悟 —— 写给正在迷茫是否要转行或去学软件测试的学弟们

本人刚从某培训机构学习结束&#xff0c;现在已经上班一个月了。这篇文章我不会说太多的知识点&#xff0c;或噱人去培训机构学习的话语&#xff0c;仅作为一个普通打工者的身份&#xff0c;来写给那些对于软件测试未来发展、薪资待遇等不清楚的正在为家庭&#xff0c;解决信用…...

IoU Loss综述(IOU,GIOU,CIOU,EIOU,SIOU,WIOU)

边界框回归&#xff08;BBR&#xff09;的损失函数对于目标检测至关重要。它的良好定义将为模型带来显著的性能改进。大多数现有的工作假设训练数据中的样本是高质量的&#xff0c;并侧重于增强BBR损失的拟合能力。 一、L2-norm 最初的基于回归的BBR损失定义为L2-norm&#xf…...

Node=>Express中间件 学习3

1.概念&#xff1a; 例&#xff1a;在处理污水的时候&#xff0c;一般都要经过三个处理环节&#xff0c;从而保证处理过后的废水&#xff0c;达到排放标准 处理污水的这三个中间处理环节&#xff0c;就可以叫中间件 2.中间件调用流程 当一个请求到达Express的服务器之后&#x…...

【STM32笔记】HAL库UART串口配置及重定向(解决接收中断与scanf不能同时工作的问题)

【STM32笔记】HAL库UART串口配置及重定向&#xff08;解决接收中断与scanf不能同时工作的问题&#xff09; 首先 要使用printf和scanf 必不可少的就是 #include <stdio.h>这里需要做的就是配置单片机的UART 并且使其能够被printf和scanf调用 打开异步工作模式 并且选择…...

使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式

一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明&#xff1a;假设每台服务器已…...

XML Group端口详解

在XML数据映射过程中&#xff0c;经常需要对数据进行分组聚合操作。例如&#xff0c;当处理包含多个物料明细的XML文件时&#xff0c;可能需要将相同物料号的明细归为一组&#xff0c;或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码&#xff0c;增加了开…...

Flask RESTful 示例

目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题&#xff1a; 下面创建一个简单的Flask RESTful API示例。首先&#xff0c;我们需要创建环境&#xff0c;安装必要的依赖&#xff0c;然后…...

iOS 26 携众系统重磅更新,但“苹果智能”仍与国行无缘

美国西海岸的夏天&#xff0c;再次被苹果点燃。一年一度的全球开发者大会 WWDC25 如期而至&#xff0c;这不仅是开发者的盛宴&#xff0c;更是全球数亿苹果用户翘首以盼的科技春晚。今年&#xff0c;苹果依旧为我们带来了全家桶式的系统更新&#xff0c;包括 iOS 26、iPadOS 26…...

Prompt Tuning、P-Tuning、Prefix Tuning的区别

一、Prompt Tuning、P-Tuning、Prefix Tuning的区别 1. Prompt Tuning(提示调优) 核心思想:固定预训练模型参数,仅学习额外的连续提示向量(通常是嵌入层的一部分)。实现方式:在输入文本前添加可训练的连续向量(软提示),模型只更新这些提示参数。优势:参数量少(仅提…...

ESP32读取DHT11温湿度数据

芯片&#xff1a;ESP32 环境&#xff1a;Arduino 一、安装DHT11传感器库 红框的库&#xff0c;别安装错了 二、代码 注意&#xff0c;DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...

将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?

Otsu 是一种自动阈值化方法&#xff0c;用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理&#xff0c;能够自动确定一个阈值&#xff0c;将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...

CocosCreator 之 JavaScript/TypeScript和Java的相互交互

引擎版本&#xff1a; 3.8.1 语言&#xff1a; JavaScript/TypeScript、C、Java 环境&#xff1a;Window 参考&#xff1a;Java原生反射机制 您好&#xff0c;我是鹤九日&#xff01; 回顾 在上篇文章中&#xff1a;CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...

【配置 YOLOX 用于按目录分类的图片数据集】

现在的图标点选越来越多&#xff0c;如何一步解决&#xff0c;采用 YOLOX 目标检测模式则可以轻松解决 要在 YOLOX 中使用按目录分类的图片数据集&#xff08;每个目录代表一个类别&#xff0c;目录下是该类别的所有图片&#xff09;&#xff0c;你需要进行以下配置步骤&#x…...

C++ 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...