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

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

  •  
  •   MinecraftFuns · 145 天前 · 618 次点击
    这是一个创建于 145 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

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

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

    希望您能帮助本蒟蒻一下

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

    谢谢

    3 回复  |  直到 2019-06-29 16:35:06 +08:00
        1
    litmxs   145 天前 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,也就是表的大小
        2
    litmxs   145 天前 via Android
    不对,查询的方式我记错了,由于是查询区间最值,查询的子区间可以重合,所以只需要查找 st[10][3]和 st[13][3],也就是小于区间长度的最大 2 的整数次幂长度的两个子区间,复杂度 O ( 1 )
        3
    zqqian   145 天前 via iPhone
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   4270 人在线   最高记录 5043   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.3 · 54ms · UTC 02:58 · PVG 10:58 · LAX 18:58 · JFK 21:58
    ♥ Do have faith in what you're doing.