今日学了一些倍增和st表的知识,前来口胡

最关键的思想就是将一个数段拆成二进制的多个部分

倍增

先来看倍增是如何解决RMQ(区间最值问题)的

我们将一个区间分开来

我们可以把一个区间$[j,j+2^i)$来分成$[j,j+2^{i-1})$和$[j+2^{i-1},2^{i})$两部分

记作一个函数$f_{i,j}=\min\limits_{k\in[j,j+2^k)} a_k$

于是有$f_{i,j}=\min(f_{i-1,j},f_{i-1,j+2^{i-1}})$

首先我们递推预处理出f数组

下面我们要查询给定的一个区间

我们对给定的区间进行二进制拆分,然后去每一部分比较取最小值

就像给出了一个长度为10的区间

$10_{(10)}=1010_{(2)}$于是我们可以将其拆成$1000_{(2)}$和$10_{(2)}$两部分

然后我们从左端点开始,首先找$f_{3,l}$与当前答案取最小值

然后将$l$增加$2^3$

然后再找$f_{1,l}$和当前答案的最小值

依此类推

最后输出答案

st表

说了那么多倍增,和st表又有什么关系呢

我们可以认为st表是一种特殊的倍增

在处理RMQ问题的时候

因为最小值,所以并不需要去分开每一段

就拿10来举例子

如果分成8+2再每一段取最小值,还需要额外进行循环来判断分段

但是我们如果分成前8+后8,结果还是一样的

所以我们找到$s=\log{(l-r+1)}$然后取

$$ f_{i,j}=\min{(f_{s,l},f_{s,r-2^s+1})} $$

直接输出答案

至于log可以用换底公式乱搞或者提前预处理

Last modification:April 12th, 2020 at 07:37 am
如果觉得我的文章对你有用,请随意赞赏