V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
MinecraftFuns
V2EX  ›  问与答

求大佬讲解一下「倍增 RMQ」算法

  •  
  •   MinecraftFuns · 2019-06-29 14:58:44 +08:00 · 1469 次点击
    这是一个创建于 1735 天前的主题,其中的信息可能已经有所发展或是发生改变。

    (算法的目的是求区间最值)

    RMQ 算法全称为(Range Minimum/Maximum Query)意思是给你一个长度为 n 的数组 A,求出给定区间的最值的下标。当然我们可以采用枚举,但是我们也可以使用线段树来优化,复杂度为(nlogn),但是最好的办法是采用Sparse_Table 算法,简称 ST 算法。它能在进行(nlogn)的预处理后达到 n(1)的效率。

    网上找了一圈教程,好像都没有理解透

    希望您能帮助本蒟蒻一下

    直接甩博客链接也是可以的,但请不要甩百度出来的前几条链接,因为我都看过了

    谢谢

    3 条回复    2019-06-29 16:35:06 +08:00
    litmxs
        1
    litmxs  
       2019-06-29 15:12:00 +08:00 via Android
    对于长度为 n 的数组 A,建立一个 n*logn 大小的表格,st[i][j]代表区间 A[i]到 A[i+2^j]中的最值
    例如求区间 10-20 的最值,我们将区间长度 11 分解为 2 的整数次幂相加( 8+2+1 ),要知道整个区间最值,我们可以查找这三个子区间 10-17,18-19,20-20,也就是 st[10][3],st[19][1],st[20][0],这样查询的复杂度就是 log
    而建立 st 表的时候利用 st[i][0]=A[i]和 st[i][j]=st[i][j-1]+st[i+2^(j-1)]两个方程建立,复杂度 nlogn,也就是表的大小
    litmxs
        2
    litmxs  
       2019-06-29 15:19:22 +08:00 via Android
    不对,查询的方式我记错了,由于是查询区间最值,查询的子区间可以重合,所以只需要查找 st[10][3]和 st[13][3],也就是小于区间长度的最大 2 的整数次幂长度的两个子区间,复杂度 O ( 1 )
    zqqian
        3
    zqqian  
       2019-06-29 16:35:06 +08:00 via iPhone
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   2813 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 28ms · UTC 14:49 · PVG 22:49 · LAX 07:49 · JFK 10:49
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.