【算法与数据结构】——倍增、ST、RMQ

偏执的太偏执、 2023-01-24 02:07 34阅读 0赞

## 简介 ##

三种原理倍增、ST、RMQ主要用于解决区间信息维护与查询问题

## 倍增 ##

倍增，顾名思义就是成倍增加。若问题的状态空间特别大，则一步步递推的算法复杂度太高，可以通过倍增思想，只考察2的整数次幂位置，快速缩小求解范围，直到找到解。

## ST ##

ST(Spare Table,稀疏表)算法采用了倍增思想，在O(nlogn)时间构造一个二维表后，可以在O(1)的时间内查询\[l,r\]区间的最值，有效解决RMQ（区间最值查询问题）

### 实现方法 ###

设F\[i,j\]表示\[i,i+ 2 j 2^j 2j\-1\]区间的最值，区间长度为 2 j 2^j 2j。初始化ST时，只需要将长度为 2 j 2^j 2j的区间划分为两个长度为 2 j − 1 2^\{j-1\} 2j−1的子区间，然后求两个子区间的最值即可。递推公式F\[i,j\]=max\{F\[i,j-1\],F\[i+ 2 j − 1 2^\{j-1\} 2j−1,j-1\]\}。

### ST创建 ###

数组长度为n；  
确定i和j的范围：i=n;  
 2 k ≤ n < 2 k + 1 2^k \\le n \\lt 2^\{k+1\} 2k≤n<2k\+1

> c++ log2() 函数表示以2为底的对数

算法代码:  
void ST\_create()\{  
//第一列是数组本身  
for(…);  
//初始化ST  
for(int j = 1;j <= k;j++)  
for(int i = 1;i<=n-(i<<j)+1;i++)  
\{F\[i\]\[j\]=max(F\[i\]\[j-1\],F\[i+(i<<j-1)\]\[j-1\])\}  
\}

### ST查询 ###

要查询区间\[l,r\]的最值，则首先要计算k值，区间长度， 2 k ≤ r − l + 1 < 2 k + 1 2^k \\le r-l+1 \\lt 2^\{k+1\} 2k≤r−l\+1<2k\+1,然后将查询区间分为两个区间，取两个区间的最值即可，两个区间分别为从l向后的 2 k 2^k 2k个数及从r向前的 2 k 2^k 2k个数，区间可能重叠，但对求最值没有影响。  
代码：  
int ST\_query(int l,int r)  
\{return max(F\[l\]\[k\],F\[r-(l<<k)+1\]\[k\]);\}

发表评论取消回复

表情：

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

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

相关阅读

相关数据结构与算法试题数据结构与算法试题

数据结构与算法试题数据结构与算法试题一、单选题1、在数据结构的讨论中把数据结构从逻辑上分为 (C ) A 内部结构与外部结构 B 静态结构与动态结构 C 线性结构与非线性结构

秒速五厘米/ 2024年03月27日 18:29/ 0 赞/ 257 阅读

相关【算法与数据结构】——倍增、ST、RMQ

简介三种原理倍增、ST、RMQ主要用于解决区间信息维护与查询问题倍增倍增，顾名思义就是成倍增加。若问题的状态空间特别大，则一步步递推的算法复杂度太高，可以通

偏执的太偏执、/ 2023年01月24日 02:07/ 0 赞/ 35 阅读

相关后缀数组倍增算法

/ 后缀数组倍增法 sa[i]表示从字符串sa[i]开始的后缀数组，排列第i S[sa[i]]<S[sa[i+1]]

深碍√TFBOYSˉ_/ 2022年09月29日 15:47/ 0 赞/ 138 阅读

相关数据结构与算法

1.二叉搜索树 1.非空左子树的所有键值小于其根节点的键值 2.非空右子树的所有键值大于其根节点的键值 3.左右子树都是二叉搜索树二叉搜索树的应用场景：如果是

Love The Way You Lie/ 2022年09月03日 01:20/ 0 赞/ 361 阅读

相关【数据结构与算法】数据结构+算法=程序

【数据结构与算法】数据结构+算法=程序数据结构数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成。记为：Data\_Struc

- 日理万妓/ 2022年08月20日 08:24/ 0 赞/ 444 阅读

相关数据结构与算法

[笨办法学 Python · 续练习 13：单链表][Python _ _ _ 13] 笨办法学 Python · 续练习 13：单链表 [数据结构与

灰太狼/ 2022年06月04日 06:16/ 0 赞/ 421 阅读

相关数据结构与算法

转自： [http://hi.baidu.com/geogre\_jsj/blog/item/e4b98fd2aab5aa3611df9b92.html][http_hi.ba

浅浅的花香味﹌/ 2022年06月04日 03:23/ 0 赞/ 693 阅读

相关算法与数据结构

常用算法的代码实现（JavaScript版）二分查找 function Binary_search(list, item){ let low = l

矫情吗；*/ 2022年03月07日 04:26/ 0 赞/ 502 阅读

相关数据结构与算法

static class TreeNode{//二叉树结点 public TreeNode(TreeNode l, TreeNode r, in

比眉伴天荒/ 2022年01月28日 23:59/ 0 赞/ 490 阅读

相关数据结构与算法

文章目录数据结构与算法介绍数据结构什么是数据结构数据结构的三要素常见的数据结构

今天药忘吃喽~/ 2021年08月19日 18:24/ 0 赞/ 673 阅读