关于RMQ的ST算法:
dp[i][j]: dp[i][i+(1<<j)-1]
dp[i][j] = min(dp[i][j-1], dp[i+2^(j-1)][j-1])

RMQ(s, t)
二分求k = log(t-s+1)
然后RMQ(s,t) = min(dp[s][k], dp[t-2^k+1][k])

这里解释一下:
t-2^k+1 - (s+2^k-1) <= 0
因为: k = log(t-s+1)
所以: t-s+1 <= 2^(k+1)
-> t-s-2^(k+1)+2 <= 2^(k+1)-1-2^(k+1)+2 = 1
说明两者之间差值不超过1, 可以覆盖一个完整的区间



阿里云系统架构:
    -分布式系统底层服务:
        -协调服务(女蜗): 基于Paxos, 支持Publish/Subscribe模式
        -远程过程调用(夸父):

    -分布式文件系统(盘古):

    -任务调度(伏羲)

    -集群监控跟部署(神农,大禹)

最近发表的文章

全部文章

评论区

comments powered by Disqus 回到顶部