首页 > 其他分享 >【数据结构】之线段树理解与基础模板

【数据结构】之线段树理解与基础模板

时间:2024-07-30 21:55:06浏览次数:12  
标签:int 线段 mid dat 区间 数据结构 节点 模板

什么是线段树

线段树 是一种通过类似 二分 来实现的一种 二叉树 结构,方便区间的修改与性质的查询,是一种非常节约时间的 数据结构

为什么使用线段树

比如我们给你 N N N 个数,每次可能对其中一个数进行修改,也可能询问区间 [ l , r ] [l,r] [l,r] 中的最大数,那么我们在查询区间中最大值的时候,可以很 暴力 暴力 暴力 地枚举一边,但这样的话时间复杂度很高,然后这时候我们其实也可以想到 分块 ,用这个方法来存下每个长度为 m m m 的区间的最大值,修改的时候再看是否有所改变,查询时整块儿整块儿去查询。但是时间复杂度受到块儿的大小以及每次询问时区间的边界与长度等因素的影响,十分不稳定,这时候我们就可以通过 线段树 来解决。

线段树的大致思路

1. 1. 1. 线段树 其实也是通过新建的 数组 来实现,数组 中的每个 节点 代表 原数组 中的一个 区间
2. 2. 2. 区间 的长度可能为 1 1 1 ,当该节点为 最底层的子节点 时,区间 的长度为 [ x , x ] [x,x] [x,x],而 根节点代表的区间长度 为 N N N ,即 根节点 代表整个数组 [ 1 , N ] [1,N] [1,N] 的一种性质。
3. 3. 3. 对于每个 不是底层的节点 ,假设其包含区间为 [ l , r ] [l,r] [l,r],则其 左子结点 代表 [ l , m i d ] [l,mid] [l,mid] ,右子节点 代表 [ m i d + 1 , r ] [mid+1,r] [mid+1,r] ,其中 m i d = ( l + r ) > > 1 mid = (l+r) >>1 mid=(l+r)>>1。
4. 4. 4. 若某节点在 线段树数组 中的下标为 x x x ,则其子节点在 线段树数组 中的下标分别为 x ∗ 2 x*2 x∗2 和 x ∗ 2 + 1 x*2+1 x∗2+1,有时我们也可以用位运算表示,分别为 x < < 1 x << 1 x<<1 和 x < < 1 ∣ 1 x << 1 | 1 x<<1∣1 。

当我们用区间表示时:

在这里插入图片描述


基础代码模板

我们这里以单点修改,区间查询最大值为例子。

线段树的声明

struct ST{int l , r , dat ;} t[N * 4];
//l和r分别表示该节点所代表区间的左右边界,dat该区间内的最大值 

线段树的建树

void build(int p , int l , int r)
{
	t[p].l = l; t[p].r = r;//记录该节点所表示的区间 
	if(l == r){return;}//此时说明是最底部节点 
	int mid = (l + r) / 2 ;
	build(p * 2 , l , mid);//建立左子结点 
	build(p * 2 + 1 , mid + 1 , r);//建立右子节点 
	t[p].dat = max(t[p * 2].dat , t[p * 2 + 1].dat);//更新区间内的最大值 
}

前文说过线段树有些 分治 的思想,那么其实也就离不开 递归 ,我们在建树的过程中相当于不断递归区间直到最底部的节点,然后向上 r e t u r n return return 来更新该区间内的最大值。

单点修改

void add(int p,int x,int v)
{
	if(t[p].l == t[p].r){t[p].dat = v ; return ;}//到达最底部节点 
	int mid = (t[p].l + t[p].r) / 2;
	if(x <= mid) add(p * 2 , x , v);//若要修改的点在该节点的左子节点 
	else add(p * 2 + 1 , x , v);//若...在右子节点 
	t[p].dat = max(t[p * 2].dat , t[p * 2 + 1].dat);//更新修改后区间的最大值 
}

区间查询最大值

int ask(int p , int l , int r)
{
	if(l <= t[p].l && r >= t[p].r) return t[p].dat;//若当前查询到的区间在询问区间范围内 
	int mid = (t[p].l + t[p].r) / 2;
	int val = -(1 << 30);
	if(l <= mid) val = max(val , ask(p * 2 , l , r));//若该区间左子结点与查询区间有重叠 
	if(r > mid) val = max(val , ask(p * 2 + 1 , l , r));//...右子节点...
	return val;//val记录该区间内的最大值,最终返还 
}

主函数中的调用

build(1 , 1 , n);//分别代表该节点在当前数组中的下标,所表示区间的左端点与右端点
add(1,b,c);//从1号节点开始,即从根节点开始,将第b个数改为c
ans = ask(1,b,c)//从1号节点开始查询,区间的左右端点分别为 b 和 c 

线段树数组 要开 4 4 4 倍
简单基础的题可以看另一篇博客【数据结构】之树状数组与线段树的咋题题面加代码不解释

标签:int,线段,mid,dat,区间,数据结构,节点,模板
From: https://blog.csdn.net/ExFoler/article/details/140806796

相关文章

  • 【数据结构】包装类和泛型
     ......
  • JavaScript 数据结构与基础算法
    数据结构全解参考:数据结构|博客园-SRIGT相关代码仓库查看:data-struct-js|Github-SR1GT0x00前置知识(1)类使用关键字class声明一个类classPerson{}JavaScript的类中通过constructor使用构建函数classPerson{constructor(name){this.name......
  • STL模板库介绍
            C++STL(StandardTemplateLibrary)是一系列提供各种数据结构和算法的模板库。        标准模板库(‌STL)‌是C++编程语言中的一个重要组成部分,‌它提供了一组通用的类和函数,‌用于实现数据结构和算法。‌        STL主要由以下几个部分组成:‌......
  • [动态开点の线段树]
    动态开点の线段树因为静态建点线段树消耗的空间太大了,需要开四倍空间,但是动态开点就可以大大降低所使用的空间,远小于四倍具体思想和线段树没有区别只是将\(k<<1\)换成了\(LS(k)\),将\(k<<1|1\)换成了\(RS(k)\),(具体开多少空间不是很能确定#include<cstdio>#include<iostream>......
  • 将dynamicTemplate添加到谷歌云模板启动
    我们使用谷歌云功能通过以下方式启动模板:https://cloud.google.com/dataflow/docs/reference/rest/v1b3/projects.locations.templates/launch我们想添加一个通过具有以下布局的动态模板将请求的暂存位置:DYNAMICTEMPLATE={"gcsPath":GCSPATH,"stagingLocation"......
  • 【数据结构】你该在什么情况下使用 LindedList
    什么是Java的LinkedList?LinkedList是Java集合框架中的一个类,位于java.util包中。它实现了List接口,并且是一个双向链表结构,可以高效地进行插入和删除操作。主要特点双向链表:每个节点包含指向前一个节点和后一个节点的引用。动态大小:链表的长度可以根据需要动态......
  • P3811 【模板】模意义下的乘法逆元 题解
    【模板】模意义下的乘法逆元题目背景这是一道模板题题目描述给定n,pn,pn,p求......
  • Pycharm 设置 yaml 格式接口测试用例模板 (python+pytest+yaml)
    前言初次编写的伙伴们可能对yaml格式不太熟悉,自己写yaml用例的时候,总是格式对不齐啊记不住设定好的关键字啊等等等琐事是我们可以在pycharm上设置用例模块,通过快捷方式调用出对应的模块,达到高效写用例的目的。 pycharm操作集:1、File-Settings(快捷键Ctrl+Alt+S) 2、Live......
  • springsecurity整合thymeleaf(thymeleaf模板引擎等价于jsp)
    创建一个springboot工程导入依赖<dependencies><dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-security</artifactId></dependency><dependency>......
  • 如何在 Django 中加载特定应用程序的模板?
    所以我正在高级学习Django,我已经知道如何包含manage.py所在的BASE_DIR中的模板。但是我想知道如何在Django中的特定应用程序中查找模板。例如,我有一个名为“mysite”的项目和一个名为polls的应用程序。现在,我在settings.pyDIRS=中添加了模板[os.path.join(BA......