Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 »  RMQ标签

LCA与RMQ互相转化

前面我们介绍过LCARMQ问题各自的解法,其实这两个问题非常类似,本质上是等价的。他们之间可以互相进行转化,并且复杂度不高,有时恰当的转化可以大大提升算法解决问题的性能,这里主要介绍二者之间互相转化的算法思想及核心代码实现。

RMQ问题的ST算法

RMQ问题(Range Minimum/Maximum Query,区间最值问题),是指给定一个长度为n的数列A,回答若干次询问RMQ(A,i,j)(i,j<=n)(通常次数非常巨大),每次返回数列A中下标在i,j里的最小(大)值。
RMQ问题解法很多,如朴素算法、线段树、ST算法RMQ与LCA互相转化等,不同算法思想及复杂度均有所差异。本文主要讲解其中非常高效的稀疏表算法(Sparse Table,ST算法)。

继续阅读»

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论