RMQ问题(超详细!!!)
in 算法 with 0 comment

RMQ问题(超详细!!!)

in 算法 with 0 comment

0x01 介绍

RMQ (Range Minimum/Maximum Query)问题是指:对于长度为$n$的数列$A$,回答若干询问$RMQ(A,i,j)(i,j<=n)$,返回数列$A$中下标在$i,j$里的最小(大)值,也就是说,RMQ​问题是指求区间最值的问题。

0x02 朴素算法

最简单的思路就是遍历查询区间$[i,j]$找最大值,如果查询次数为q,那么这种算法的时间复杂度O(nq)

0x03 Sparse Table算法

我们定义函数$f(i,j)$表示以$i$起始,包含$2^j$个点的区间的最大值,那么:

也就是将区间[i,i+(1<<j)-1]拆分为了[i,i+(1<<(j-1))-1][i+1<<(j-1),i+(1<<j)-1],这种算法的时间复杂度O(nlogn)

0x0301 一维

const int MAXN = 50010;
int dp[MAXN][20];
int mm[MAXN];  // 存储对数
//初始化RMQ, b 数组下标从1 开始,从0 开始简单修改
void initRMQ(int n, int b[])
{
    mm[0] = −1;
    for (int i = 1; i <= n; i++)
    {
        mm[i] = ((i & (i − 1)) == 0) ? mm[i − 1] + 1: mm[i − 1];
        dp[i][0] = b[i];
    }
    
    for (int j = 1; j <= mm[n]; j++)
        for (int i = 1; i + (1 << j) − 1 <= n; i++)
            dp[i][j] = max(dp[i][j − 1], dp[i + (1 << (j − 1))][j − 1]);
}
//查询最大值
int rmq(int x, int y)
{
    int k = mm[y − x + 1];
    return max(dp[x][k], dp[y − (1 << k) + 1][k]);
}

其中(i & (i − 1)) == 0来判断n是不是2的整次幂。这里将二维st算法也记录下来。

0x0301 二维

int val[310][310];
int dp[310][310][9][9];//最大值
int mm[310];//二进制位数减一,使用前初始化
void initRMQ(int n, int m)
{
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            dp[i][j][0][0] = val[i][j];

    for (int ii = 0; ii <= mm[n]; ii++)
    {
        for (int jj = 0; jj <= mm[m]; jj++)
        {
            if (ii + jj)
            {
                for (int i = 1; i + (1 << ii) − 1 <= n; i++)
                {
                    for (int j = 1; j + (1 << jj) − 1 <= m; j++)
                    {
                        if (ii) dp[i][j][ii][jj] = max(dp[i][j][ii − 1][jj], dp[i + (1 << (ii − 1))][j][ii − 1][jj]);
                        else dp[i][j][ii][jj] = max(dp[i][j][ii][jj − 1], dp[i][j + (1 << (jj − 1))][ii][jj − 1]);
                    }
                }
            }
        }
    }
}
//查询矩形内的最大值(x1 <= x2,y1 <= y2)
int rmq(int x1, int y1, int x2, int y2)
{
    int k1 = mm[x2 − x1 + 1];
    int k2 = mm[y2 − y1 + 1];
    x2 = x2 − (1 << k1) + 1;
    y2 = y2 − (1 << k2) + 1;
    return max({dp[x1][y1][k1][k2], dp[x1][y2][k1][k2], dp[x2][y1][k1][k2], dp[x2][y2][k1][k2]});
}

0x04 RMQ问题与LCA问题

LCA问题就是最近公共最先问题:对于有根树$T$的两个结点$u、v$,最近公共祖先$LCA(T,u,v)$表示一个结点$x$,满足$x$是$u$和$v$的祖先且$x$的深度尽可能大。在这里,一个节点也可以是它自己的祖先。

RMQ问题和LCA问题之间可以相互转化。

0x0401 RMQ问题转化为LCA问题

首先将数列A构建成笛卡尔树,然后在笛卡尔树上使用RMQ算法求解最近公共祖先。

此时区间[l,r]的最小值即为lr的最近公共祖先,而RMQ(l, r)可以在O(1)时间内求解。

0x0402 LCA问题转化为RMQ问题

通过dfs遍历树,得到树的欧拉序列,将序列A中对应点添加树的深度。

那么此时区间d[l,r]的最小值就是lr的最近公共祖先,同样也就是RMQ(A[l,r])的解。

此时,我们注意到d数组中前后两个元素的差值为+1/-1,那么这其实是一种特殊的RMQ,称为+1/-1 RMQ问题,这类问题存在O(n)的预处理算法。

0x05 O(n)时间处理RMQ问题

RMQ问题可以在O(n)时间内处理,主要分成三步:

0x0501 +1/-1 RMQ问题

对长度为n的序列,按照长度s=log(n)/2分割成B=2n/log(2)块,然后计算每个块的最小值。

此时我们对于RMQ问题就分成了:1)左右块的内部查询 2)中间块之间查询。问题一可以采用Sparse Table算法处理,时间复杂度就是O(BlogB)=O(2n/log(n)*(log(2n)-log(log(n))))=O(n)。问题二可以采用查表法,因为每两个元素之间的关系只有两种(+1/-1),所以本质不同的块最多有2^s=sqrt(n)种。为了可以在O(1)时间内查询块内的最小值,我们在O(s^2)的时间内建立一个s^2大小的查找表(实际上只需要上三角大小即可)。对每种块中所有可能的块内查询预处理出答案的复杂度是O(sqrt(n)*s^2)=O(N)(这里的O(N)表示不超过线性时间。预处理出所有块的“类型”,并用二进制数存储的时间复杂度是O(N)。具体实现这里就不实现了,太麻烦了~

reference:

https://baike.baidu.com/item/rmq/1797559?fr=aladdin

https://www.slideshare.net/yumainoue965/lca-and-rmq

https://baike.baidu.com/item/最近公共祖先/8918834?fr=aladdin

如有问题,希望大家指出!!!

「如果我的文章对你有很大帮助,那么不妨~!」

coordinate

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses