一.倍增
倍增是一种常用的算法技巧,通常用于优化时间复杂度。它的核心思想是将原问题分解成若干个规模较小的子问题,通过对子问题的求解来得到原问题的解。具体来说,倍增算法通常采用二分思想,将问题规模不断缩小,直到问题规模足够小,可以直接求解。
在计算机科学中,倍增算法通常用于解决一些需要快速求解的问题,例如最近公共祖先、区间最大值、区间和等问题。通过采用倍增算法,可以将这些问题的时间复杂度从O(n)降低到O(logn),从而大大提高算法的效率。
二.ST表
ST表(Sparse Table)是一种用于解决区间查询问题的数据结构。它可以在O(1)的时间复杂度内回答区间最值查询问题,如区间最大值、最小值等。
ST表的构建过程是基于动态规划的思想。首先,我们需要预处理出一个二维数组dp,其中dp[i][j]表示从位置i开始,长度为2^j的区间内的最值。然后,通过递推的方式,我们可以得到dp数组的所有值。
构建ST表的时间复杂度为O(nlogn),其中n是原始数组的长度。一旦ST表构建完成,我们可以在O(1)的时间内回答任意区间的最值查询。
ST表的应用非常广泛,特别是在解决静态区间查询问题时非常有效。例如,在解决最长公共前缀、区间最大值、区间最小值等问题时,ST表都可以提供高效的解决方案。
需要注意的是,ST表适用于静态数据,即查询操作多而修改操作少的情况。如果数据是动态变化的,需要频繁进行修改操作,那么ST表可能不是最优的选择,可以考虑其他数据结构,如线段树。
三.模板题
P3865 【模板】ST 表 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
四.参考代码
#include<bits/stdc++.h>
#define maxn 100005
using namespace std;
int f[maxn][30];
int n,m;
int query(int l,int r){
int k=log2(r-l+1);
return max(f[l][k],f[r+1-(1<<k)][k]);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&f[i][0]);
//初始化
for(int j=1;(1<<j)<=n;j++){
for(int i=1;i<=n+1-(1<<j);i++){
f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}
}
for(int i=1;i<=m;i++){
int l,r;
scanf("%d%d",&l,&r);
printf("%d\n",query(l,r));
}
return 0;
}
五.范围解释
(1)j的范围:
因为j为长度,显然长度不能大于n,即(1<<j)<=n;
(2)i的范围
因为长度为1<<j,所以n-i+1<=1<<j。 然后移项即可
文章来源:https://www.toymoban.com/news/detail-675746.html
尽可能取最大长度,f[r+1-(1<<k)][k]是由有边界为r,长度为1<<k推出来的。文章来源地址https://www.toymoban.com/news/detail-675746.html
到了这里,关于【算法】倍增-ST表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!