线段树+rmq问题第二弹

detrol detrol     2022-09-19     180

关键词:

技术分享

 

 

技术分享

 

技术分享

线段树+RMQ问题第二弹

 

 

上篇文章讲到了基于Sparse Table 解决 RMQ 问题,不知道大家还有没有印象,今天我们会从线段树的方法对 RMQ 问题再一次讨论。

正式介绍今天解决 RMQ 问题的方法之前,我先对 RMQ 问题的概念再一次进行说明。RMQ (Range Minimum/Maximum Query ):中文名为“区间最值查询”。RMQ 问题指的是给定一段区间,针对给定区间进行若干次查询,每次给出不同的待查询子区间范围,要求返回子区间内的最大值或者最小值。

RMQ 问题可以看作是线段树的一个应用,本来今天的主角是 RMQ 问题,但我思前想后觉得草草解释线段树或者只展示RMQ一个方面的应用留个小尾巴有点意犹未尽,之前没有接触过线段树的朋友也会觉得云里雾里,因此我改变主意决定以线段树的基本概念和应用作为今天的主要内容,RMQ问题的解决作为整篇文章的一个实例,下面就要进入主题了。

技术分享

 

线段树是什么?线段树是一种完美的树,这种树对于处理区间问题有相当高的效率。线段树满足这样一些特点:

一、是一棵完全二叉树,除最后一层之外其余各层均是满的,所有的叶节点均排布在最后一层,所有的节点不是叶节点就是拥有两棵子树的节点。

二、每个节点维护一段区间,其中根节点维护的是整个区间,其余节点均维护的是直接父节点的二分之一区间,也就意味着将父节点维护的区间二等分分别分给左右两个孩子维护。

三、根据节点维护的数据不同,线段树可以实现不同的功能。

四、并非所有的区间问题都可以用线段树来解决。

这样不形象的用文字描述就想让没接触过的人了解线段树实在有点强人所难,我还是画一张丑图来说明一下吧。如下图所示:

技术分享

以求 RMQ 问题为例我们来深入了解一下有关线段树的性质,假设本篇文章我们的要求是求区间最小值。

由上图可知,该图中的线段树维护的是 n = 8 的区间的数据,每个节点存储的是所维护区间内的最小值,该线段树的深度为 L 。通常情况下整个线段树各节点的值会存储在数组里边,因此我们需要知道线段树的节点数。假设 区间的元素个数为 n ,线段树的深度为 L ,线段树的节点数为 m 。

由上图可知三者满足的关系为:

L = log n +1(对数以 2 为底);即 2^(L-1) = n 

 

m = 2^0 + 2^1 + 2^2 + 2^3 + ......+ 2^( L - 1)

m =( 2^0 + 2^0 )+ 2^1 + 2^2 + 2^3 +...... + 2^( L-1) -1

m = (2^1 + 2^1) + 2^2 + 2^3 +......+ 2^(L-1) - 1

... ...

m = 2^(L-1) + 2^(L-1) -1

m = n + n -1

m = 2n-1

 

由上面的推导过程可以知道,m = 2n-1是妥妥的。没求证之前,可能很多人看到线段树的图之后,都会觉得规模应该是 O(n log n),虽然不知道这种错觉的理由是什么,但是知道了一点,以后凡事都需要自己亲自验证一番才能彻底打消错误的念头。这也就意味着对线段树的初始化是O(n)的时间复杂度。

现在我们来看一下求区间最值具体是怎样实现的。首先我们知道线段树上存储的是一些固定区间的最值,因此我们要求一些自定义区间的最值时,需要同时结合线段树上的若干个连续区间的多个最值,在其中选择最小的作为最后的结果,由于将整个区间分成若干子区间分别求最值最后合并结果的方法对最后结果的正确性没有影响,因此存在实现上的可行性。那么对于自定义的一个区间,在线段树上具体需要选取哪些区间呢?我们需要选取的是能够完全被自定义区间覆盖的那些区间。对于线段树上的任何一个区间,可能执行的操作有三个:

若该区间中的所有元素均包含在自定义区间中,那么直接返回线段树上存储的该区间最值。

若该区间的所有元素中任何一个元素都不曾出现在自定义区间中,那么自定义区间的最值一定不会来自该区间,这时候返回一个不影响结果判断的值即可。

若该区间既不能被自定义区间完全包含,又存在若干元素包含在自定义区间中,那么递归的对该区间对应的两个子区间分别执行这三个判断。

大概思路就是如此。

 

虽然将普通区间改造为线段树来维护没有增加过多的任务量,由上面的分析可以知道这么做的效果却是很惊人的,因为利用线段树求区间最值的时候,在树的每一层至多需要访问两个节点,由上至下共 L = log n +1层,也就意味着,找到一个区间的最值需要访问的节点数 至多都不会超过 2 * L - 1 ,因此查找一次区间最值时间复杂度稳定在 O( log n)的时间复杂度,这可是个惊人的发现呢。 

 

技术分享

线段树的另一个比较有名的应用就是修改区间上某一位置的值,可以从线段树的最底层开始修改,由于在任何一层每个元素只可能出现在一个区间,因此修改一个值的时间复杂度恒为O(log n)。

 

线段树的两个比较常见的应用都在这里,理论描述上面已经给出,接下来我将核心代码部分附上供大家对细节进行推敲。图片看不清楚的朋友可打开网页http://paste.ubuntu.com/25418076/查看网页版的代码。

 

技术分享

 

技术分享

技术分享

今天的分享就到这里,有朋友发现文章中写的不合适的地方可以直接在下方留言区留言纠正。

技术分享

没有关注公众号的朋友,可以识别下方二维码关注我。

 

技术分享

 

 

 


 

技术分享

 

树状数组区间更新

...新 在今天的文章开始之前,给大家提一个建议,由于线段树和树状数组这两个结构的分析有很多联系,因此,建议没有看前几篇文章的朋友一定需要了解一下前面的内容。链接如下:线段树+RMQ问题第二弹线段树第二弹(区... 查看详情

codeforces620enewyeartree(线段树的骚操作第二弹)(代码片段)

TheNewYearholidaysareover,butReshadoesn‘twanttothrowawaytheNewYeartree.HeinvitedhisbestfriendsKerimandGuraltohelphimtoredecoratetheNewYeartree.TheNewYeartreeisanundirectedtreewith n vertices 查看详情

rmq类问题利器:线段树(代码片段)

文章目录线段树一、问题引入二、线段树的构建三、线段树的单点修改与查询1、修改2、查询四、线段树的区间修改与查询1、修改2、查询五、离散化线段树六、算法练习[LeetCode307单点修改问题](https://leetcode.cn/problems/range-sum-query-... 查看详情

rmq类问题利器:线段树(代码片段)

文章目录线段树一、问题引入二、线段树的构建三、线段树的单点修改与查询1、修改2、查询四、线段树的区间修改与查询1、修改2、查询五、算法练习[LeetCode307单点修改问题](https://leetcode.cn/problems/range-sum-query-mutable/)[LeetCode732区... 查看详情

uva12299带循环移动的rmq(线段树)

...循环移动(往前移动)。分析:求区间问题,很容易想到线段树,西东就相当于单点更新。建树,有两种方案,第一种是nlogn,就是不断的更新,更新logn,有n个数。1#include<bits/stdc++.h>23usingnamespace 查看详情

[luogup1816]忠诚(rmq||线段树)

传送门 其实我就是想练练rmq本以为学了线段树可以省点事不学rmq了但是后缀数组中用rmq貌似很方便所以还是学了吧,反正也不难 ——代码1#include<cstdio>2#defineN1000013#definemin(x,y)((x)<(y)?(x):(y))45intn,m;6inta[N],d[N][21]... 查看详情

#rmq,动态开点线段树#cf803gperiodicrmqproblem(代码片段)

RMQ,动态开点线段树题目给定\\(n\\)个数,将这个数列复制\\(k\\)次得到数列\\(a\\),对\\(a\\)满足区间赋值操作和区间最小值询问\\(n\\leq10^5,q\\leq10^5,k\\leq10^4即|a|\\leq10^9\\)分析先考虑线段树的区间赋值和区间最小值询问,如果没有复... 查看详情

hihocoderweek19rmq问题再临-线段树单点更新区间查询(代码片段)

单点更新区间查询 #include<bits/stdc++.h>usingnamespacestd;#definem((l+r)/2)#definels(rt<<1)#definers(rt<<1|1)constintN=2e6+10;ints[N],tr[N];voidbuild(intrt,intl,intr)if(l==r)tr[rt]=s[ 查看详情

uva11235frequentvalues线段树/rmq

  vjudge上题目链接:UVA11235*******************************************************大白书上解释************************************************************  题目大意:给出一个非降序排列的整数数组a1,a2,a3,...,an,你的任务是对于一系列询问(i,j),回... 查看详情

[拆位线段树]rmq(代码片段)

[拆位线段树]RMQ题目https://ac.nowcoder.com/acm/problem/21414思路区间或,区间求和对于区间或,异或这种位运算,没法之间打懒标记。但是如果我们按位拆分,可以发现对于原数组都为01的线段树来说,或运算等效于... 查看详情

liaoliao的四连做第二弹

liaoliao四连做第一弹1.bzoj3211:花神游历各国由于$10^9$以内的数最多只会被开方$10$次,所以我们可以用线段树维护然后剪枝..#include<cstdio>#include<cstring>#include<cstdlib>#include<algorithm>#include<cmath>#defineLLlon 查看详情

蓝书4.1-4.4树状数组rmq问题线段树倍增求lca(代码片段)

这章的数据结构题很真实T1排队bzoj1699题目大意:求静态一些区间的最大值-最小值思路:ST表裸题1#include<iostream>2#include<cstdio>3#include<cstdlib>4#include<cstring>5#include<cmath>6#include<algorithm>7#inc 查看详情

pku2823slidingwindow(线段树||rmq||单调队列)

#include<cstdio>#include<algorithm>#definemaxn1000005#defineinf0x3f3f3f3fusingnamespacestd;intSegtree_min[maxn<<2],Segtree_max[maxn<<2];intn,k,value;intbegin,end;//每个结点保存该区间线段的 查看详情

lca欧拉序+rmq(st)欧拉序+rmq(线段树)离线dfs(代码片段)

https://www.luogu.org/problemnew/show/P3379 1.欧拉序+rmq(st) 1/*2在这里,对于一个数,选择最左边的3选择任意一个都可以,[left_index,right_index],深度都大于等于这个数的深度4*/5#include<cstdio>6#include<cstdlib>7#include< 查看详情

poj2763(lca/rmq+线段树)

题目链接:http://poj.org/problem?id=2763 题意:第一行输入n,q,s分别为树的顶点个数,询问/修改个数,初始位置.接下来n-1行形如x,y,w的输入为点x,y之间连边且边权为w.接下来q行输入,若输入形式为1xy则为将点x的权值修改为y,若输入形式为0... 查看详情

一码学程10284排队找bug题解单调队列或者线段树rmq(代码片段)

注:只是看到题目,未评测,所以不确定代码正确性,但是算法思路没有问题描述同学们的bug还真是多啊,orz...春节期间大家存下的bug都来找肖老师解决了。每个人都有bug,但是肖老师却只有一个啊。怎么办?所以肖老师让大家... 查看详情

rmq_第一弹_sparsetable(代码片段)

...询问一个区间内的最值问题,,,暑假集训的时候学习了线段树,,,也可以对给定数组查询任意区间的最值问题,,,,这两个主要的区别就是线段树可以 查看详情

rmq算法

...决这两种问题的比较高效的算法。当然,该问题也可以用线段树(也叫区间树)解决,算法复杂度为:O(N)~O(logN),这里我 查看详情