【模版】Sparse-Table｜ST表｜基于ST表的RMQ

﹏ヽ暗。殇╰゛Y 2022-12-28 12:46 230阅读 0赞

### 文章目录 ###

*  Sparse Table（ST表）
 *  详细介绍
 *  模版(最小值版本)

--------------------

# Sparse Table（ST表） #

**通过O(n\*logn)的预处理，以及O(n\*logn)的空间，达到O(1)时间复杂度的查询操作**

**常用于对*静态*RMQ问题进行求解**

*  d\[i\]\[j\]代表着这样一个区间的最值：左端点为 **i** ，长度为 **2j** 的区间，即区间\*\*\[i, i + 2j \- 1\]\*\*

例如：

d\[5\]\[3\] = min(d\[5\]\[2\], d\[9\]\[2\])，即意味着min(5, 12) = min( min(5…8), min(9…12) )，即`区间5～12的最值`，等于 `5～8的最值和9～12的最值` 的`最值`

# 详细介绍 #

https://blog.csdn.net/guoyangfan\_/article/details/81147253

https://www.luogu.com.cn/blog/zhouziheng666/qian-tan-st-biao

# 模版(最小值版本) #

来源：https://www.cnblogs.com/autsky-jadek/p/7327416.html

int d[1000006][25];
    int mn[1000006];
    void rmq_init()
    {
        
        for(int i = 1; i <= n; i++)
            d[i][0] = a[i];
        for(int j = 1; (1 << j) <= n; j++)
          for(int i=1;i+(1<<j)-1<=n;i++)
            d[i][j]=min(d[i][j-1],d[i+(1<<(j-1))][j-1]);
        for(int len=1;len<=n;++len){
        
            int k=0;
            while((1<<(k+1))<=len)
                k++;
            mn[len]=k;
        }
    }
    int rmq(int L,int R)
    {
        
        int k=mn[R-L+1];
        return min(d[L][k],d[R-(1<<k)+1][k]);
    }

如果需要求出最大值，修改两个位置即可

d[i][j] = max(d[i][j-1], d[i + (1 << (j - 1))][j - 1]);

return max(d[L][k], d[R - (1 << k) + 1][k]);

发表评论取消回复

表情：

评论列表（有 0 条评论，230人围观）

还没有评论，来说两句吧...

相关阅读

相关 ST表

ST表什么是ST表 ST表是一种神奇的数据结构，它虽说有它的短板——不支持修改，但它的特点同样很鲜明——短小精悍，能做到 $ O (n \\log n) ...

谁践踏了优雅/ 2024年04月20日 10:34/ 0 赞/ 153 阅读

相关 hihoCoder 1068 : RMQ-ST算法（区间最值查询之 rmq算法）

\1068 : RMQ-ST算法时间限制: 10000ms 单点时限: 1000ms 内存限制: 256MB <table></table> 描述小Hi

柔光的暖阳◎/ 2024年02月17日 21:46/ 0 赞/ 100 阅读

相关【模版】Sparse-Table｜ST表｜基于ST表的RMQ

文章目录 Sparse Table（ST表）详细介绍模版(最小值版本) -------------------- Sparse Table（S

﹏ヽ暗。殇╰゛Y/ 2022年12月28日 12:46/ 0 赞/ 231 阅读

相关 ST算法求解RMQ问题的模板

ST算法主要用来快速求解某个区间的最大/小值问题（RMQ问题），需要借助于一个二维数组dp进行预处理，预处理的时间复杂度为O(nlogn)，预处理的过程主要使用了倍增的思想，查

谁借莪１个温暖的怀抱￠/ 2022年08月29日 09:57/ 0 赞/ 221 阅读

相关 POJ 3264-Balanced Lineup（RMQ-ST算法）

Balanced Lineup <table> <tbody> <tr> <td><strong>Time Limit:</strong> 500

ゝ一纸荒年。/ 2022年06月18日 10:54/ 0 赞/ 285 阅读

相关 RMQ ST算法

概述: RMQ（Range Minimum/Maximum Query），即区间最值查询，是指这样一个问题：对于长度为n的数列A，回答若干询问RMQ（A,i,j）(i,j

浅浅的花香味﹌/ 2022年06月14日 08:26/ 0 赞/ 309 阅读

相关 ST表

转载博主:[点这里][Link 1] ST表学习作用：ST算法是用来求解给定区间RMQ的最值，本文以最小值为例举例：给出一数组A\[0~5\] = \{5,4

￡神魔★判官ぃ/ 2022年05月28日 07:25/ 0 赞/ 302 阅读

相关 st 表算法模板

借鉴于：[https://blog.csdn.net/Hanks\_o/article/details/77547380][https_blog.csdn.net_Hanks_

左手的ㄟ右手/ 2022年05月15日 12:23/ 0 赞/ 304 阅读

相关浅谈ST表

咱们先来前情引导一下　　假如你的面前有一个区间【1，6，2，8，7，4，6，3，9，3，0】请问，这个区间的最大值是森魔？最小值是森魔？（千万别说你不知道）答案显然：m

雨点打透心脏的1/2处/ 2021年11月05日 12:24/ 0 赞/ 369 阅读

相关 ST表模板

普通存最大值，最小值 int a[maxn]; ll Max[MAXN][21]; ll Query(int l,int r) {

梦里梦外;/ 2021年09月19日 05:40/ 0 赞/ 340 阅读