ST表(跳跃表)

最新推荐文章于 2025-03-29 19:23:45 发布
最新推荐文章于 2025-03-29 19:23:45 发布
阅读量257 收藏
点赞数
分类专栏： 数据结构 文章标签： 算法 数据结构 c语言
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/hacker__man/article/details/125913933
版权

ST表(跳跃表)

解决静态区间最大值问题， O ( N l o g N ) O(NlogN) O(NlogN)预处理后， O ( 1 ) O(1) O(1)给出数列 A A A中下标在 l ∼ r l \sim r l∼r之间的数的最大值是多少

F [ i , j ] 表示数列 A 下标中在 A [ i , i + 2 j − 1 ] 区间的最大长度， i ∼ i + 2 j − 1 共 2 j 个数字 递推边界 F [ i , 0 ] = A [ i ] , 根据公式 F [ i ] [ j ] = m a x ( F [ i ] [ j − 1 ] , f [ i + 2 j − 1 ) ] [ j − 1 ] ) 询问时找出小于区间长度下最大的 K 次幂，因为 F [ l ] [ k ] , F [ r − 2 k + 1 ] [ k ] 一定可以覆盖 [ l , r ] O ( 1 ) 询问即可 F[i,j]表示数列A下标中在A[i,i+2^j-1]区间的最大长度，i \sim i+2^j-1 共2^j个数字\\递推边界F[i,0]=A[i],根据公式F[i][j]=max(F[i][j-1],f[i+2^{j-1})][j-1])\\ 询问时找出小于区间长度下最大的K次幂，因为F[l][k],F[r-2^k+1][k]一定可以覆盖[l,r]\\ O(1)询问即可 F[i,j]表示数列A下标中在A[i,i+2j−1]区间的最大长度，i∼i+2j−1共2j个数字递推边界F[i,0]=A[i],根据公式F[i][j]=max(F[i][j−1],f[i+2j−1)][j−1])询问时找出小于区间长度下最大的K次幂，因为F[l][k],F[r−2k+1][k]一定可以覆盖[l,r]O(1)询问即可

P3865 【模板】ST 表

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <queue>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#define pb push_back 
#define mem(f, x) memset(f,x,sizeof(f)) 
#define fo(i,a,n) for(int i=(a);i<=(n);++i)
#define fo2(i,a,n) for(int i=(a);i<(n);++i)
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;

typedef long long ll;
const int N=1e6;

int w[N],n,m,M,f[N][20];

struct _ST
{
	/*
	O(NlogN)预处理区间最值，O(1)查询,数组下标从1开始 
	M=log(n)/log(2)+1;
	由于在class外部不允许访问私有成员，所以这将导致编译出错。
	*/
	void init(){
		memset(f,-1,sizeof f);
		for(int j=0;j<M;j++){
			for(int i=1;i+(1<<j)-1<=n;i++){
				if(!j)f[i][j]=w[i];
				else f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
			}
		}
	}
	int query(int l,int r){
		int k=log(r-l+1)/log(2);
		return max(f[l][k],f[r-(1<<k)+1][k]);
	}
}_ST;

int main()
{
	cin>>n>>m;
	
	for(int i=1;i<=n;i++)scanf("%d",&w[i]);
	
	_ST.init();
	
	for(int i=1;i<=m;i++){
		int l,r;
		scanf("%d%d",&l,&r);
		printf("%d\n",_ST.query(l,r));
	} 
	
	return 0;
}

P2251 质量检测

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <queue>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#define pb push_back 
#define mem(f, x) memset(f,x,sizeof(f)) 
#define fo(i,a,n) for(int i=(a);i<=(n);++i)
#define fo2(i,a,n) for(int i=(a);i<(n);++i)
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;

typedef long long ll;
const int N=1e6;

int w[N],n,m,M,f[N][20];

struct _ST
{
	/*
	O(NlogN)预处理区间最值，O(1)查询,数组下标从1开始 
	M=log(n)/log(2)+1;
	由于在class外部不允许访问私有成员，所以这将导致编译出错。
	*/
	void init(){
		memset(f,0x3f,sizeof f);
		for(int j=0;j<M;j++){
			for(int i=1;i+(1<<j)-1<=n;i++){
				if(!j)f[i][j]=w[i];
				else f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);
			}
		}
	}
	int query(int l,int r){
		int k=log(r-l+1)/log(2);
		return min(f[l][k],f[r-(1<<k)+1][k]);
	}
}_ST;

int main()
{
	cin>>n>>m;
	M=log(n)/log(2)+1;
	for(int i=1;i<=n;i++)scanf("%d",&w[i]);
	
	_ST.init();
	
	for(int i=1;i+m-1<=n;i++){
		int l=i,r=l+m-1;
		printf("%d\n",_ST.query(l,r));
	} 
	return 0;
}

P1816 忠诚

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <queue>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#define pb push_back 
#define mem(f, x) memset(f,x,sizeof(f)) 
#define fo(i,a,n) for(int i=(a);i<=(n);++i)
#define fo2(i,a,n) for(int i=(a);i<(n);++i)
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;

typedef long long ll;
const int N=1e5+10;

int w[N],n,m,M,f[N][20];

struct _ST
{
	/*
	O(NlogN)预处理区间最值，O(1)查询,数组下标从1开始 
	M=log(n)/log(2)+1;
	由于在class外部不允许访问私有成员，所以这将导致编译出错。
	*/
	void init(){
		memset(f,0x3f,sizeof f);
		for(int j=0;j<M;j++){
			for(int i=1;i+(1<<j)-1<=n;i++){
				if(!j)f[i][j]=w[i];
				else f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);
			}
		}
	}
	int query(int l,int r){
		int k=log(r-l+1)/log(2);
		return min(f[l][k],f[r-(1<<k)+1][k]);
	}
}_ST;

int main()
{
	cin>>n>>m;
	M=log(n)/log(2)+1;
	for(int i=1;i<=n;i++)scanf("%d",&w[i]);
	
	_ST.init();
	
	for(int i=1;i<=m;i++){
		int l,r;
		scanf("%d%d",&l,&r);
		printf("%d ",_ST.query(l,r));
	} 
	
	return 0;
}

P2880 [USACO07JAN]Balanced Lineup G

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <queue>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#define pb push_back 
#define mem(f, x) memset(f,x,sizeof(f)) 
#define fo(i,a,n) for(int i=(a);i<=(n);++i)
#define fo2(i,a,n) for(int i=(a);i<(n);++i)
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;

typedef long long ll;
const int N=1e5+10;

int w[N],n,m,M,f_max[N][16],f_min[N][16];

struct _ST
{
	/*
	O(NlogN)预处理区间最值，O(1)查询,数组下标从1开始 
	M=log(n)/log(2)+1;
	由于在class外部不允许访问私有成员，所以这将导致编译出错。
	*/
	void init(){
		memset(f_min,0x3f,sizeof f_min);
		memset(f_max,-1,sizeof f_max);
		for(int j=0;j<M;j++){
			for(int i=1;i+(1<<j)-1<=n;i++){
				if(!j)f_min[i][j]=w[i];
				else f_min[i][j]=min(f_min[i][j-1],f_min[i+(1<<(j-1))][j-1]);
			}
		}
		for(int j=0;j<M;j++){
			for(int i=1;i+(1<<j)-1<=n;i++){
				if(!j)f_max[i][j]=w[i];
				else f_max[i][j]=max(f_max[i][j-1],f_max[i+(1<<(j-1))][j-1]);
			}
		}
	}
	int query_min(int l,int r){
		int k=log(r-l+1)/log(2);
		return min(f_min[l][k],f_min[r-(1<<k)+1][k]);
	}
	int query_max(int l,int r){
		int k=log(r-l+1)/log(2);
		return max(f_max[l][k],f_max[r-(1<<k)+1][k]);
	}
}_ST;

int main()
{
	cin>>n>>m;
	M=log(n)/log(2)+1;
	for(int i=1;i<=n;i++)scanf("%d",&w[i]);
	
	_ST.init();
	
	for(int i=1;i<=m;i++){
		int l,r;
		scanf("%d%d",&l,&r);
		printf("%d\n",_ST.query_max(l,r)-_ST.query_min(l,r));
	} 
	
	return 0;
}
ST表
唐大帅
04-15 1372
P3865 【模板】ST表 题目背景 这是一道ST表经典题——静态区间最大值 请注意最大数据时限只有0.8s，数据强度不低，请务必保证你的每次查询复杂度为O(1) 题目描述 给定一个长度为N的数列，和M次询问，求出每一次询问的区间内数字的最大值。 输入输出格式 输入格式： 第一行包含两个整数N, M 分别表示数列的长度和询问的个数。 第二行包含N个整数（记为 ...
专题三（栈，队列，优先队列，ST表）
hhhh_w_w的博客
02-07 997
栈是一种(Last In, First Out) 的容器适配器，仅支持查询或删除最后一个加入的元素 （栈顶元素），不支持随机访问，且为了保证数据的严格有序性，不支持迭代器。
ST 表——详解
最新发布
w_w_wwwww的博客
03-29 293
ST 表（Sparse Table，稀疏表）是用于解决可重复贡献问题的数据结构。什么是可重复贡献问题？可重复贡献问题是指对于运算，满足，则对应的区间询问就是一个可重复贡献问题。例如，最大值有，gcd 有，所以 RMQ 和区间 GCD 就是一个可重复贡献问题。像区间和就不具有这个性质，如果求区间和的时候采用的预处理区间重叠了，则会导致重叠部分被计算两次，这是我们所不愿意看到的。另外，还必须满足结合律才能使用 ST 表求解。什么是 RMQ？
学习笔记——ST表
Tricksterism
02-12 225
学习笔记——ST表 作用： 给定一个数列 ai O(nlogn) 预处理 O(1) 查询区间最值 实现： 定义f(i,j) 为ai开始，包括ai的连续2^j个元素的最值 下面以最大值为例： f(i,j)表示max{ak}(k∈[i,i+2^j)). 利用倍增： f[i][j]= {aimax(f[i][j−...
（PWM控制）音量电平表电路+PCB源文件+源代码+上位机等-电路方案
04-22
VU电平表显示代码，正如你所见，这个软件可以进行一堆个性化的设置，你可以设置显示阻尼（Display damping ，它跟随音乐跳跃的速率，更大的阻尼使跳跃更缓和，但是有失精准），可以设置淡出速度（fade off ），也...
`算法知识` 倍增, 可重复贡献问题, ST打表
WChang的博客
08-12 357
1
深度学习：STGCN学习笔记
热门推荐
zhe470719的博客
11-10 2万+
目录标题基于图神经网络的图分类问题GCN在行为识别领域的应用主要任务研究思路ST-GCN(SpatialTemporal Graph Convolutional Networks for Skeleton-Based Action Recognition)解读原论文解决问题主要贡献核心思想简介OpenPose 预处理基于人体关键点构造graph构造单帧graph（空间域）构造帧间graph（时间域）ST-GCN模型采样函数权重函数空域图卷积空间-时间模型分区策略可学习的边重要性权重TCNST-GCN模型的实
【STL源码剖析】总结笔记（10）：哈希表（hashtable）探究
斯塔克家的真维斯的工作间
11-30 948
00 写在前面 平衡二叉搜索树中的RB-tree作为一种效率表现和复杂度很平衡的结构，一直被用作STL set和map的底层支持。 【STL源码剖析】总结笔记（8）：红黑树（RB-tree）探究 【STL源码剖析】总结笔记（9)：set/multiset与map/multimap 而还有一种结构，哈希表（以下称hashtable），在数据具有足够的随机性时，也能够保持在插入删除等操作上的“常数平均时间”表现。也是unordered结构的基础。 hashtable更多的是经验设计 01 概述 hasht
Java 稀疏表是什么
02-28
4. **幂次跳跃**：基于区间长度为$2^k$的预处理 --- ### 二、实现原理 #### 1. 预处理阶段 构建二维数组`st[][]`，其中： $$st[i][k] = \text{区间}[i, i+2^k-1]\text{的查询结果}$$ ```java // Java示例：构建...
评论
添加红包

请填写红包祝福语或标题

个

红包个数最小为10个

元

红包金额最低5元

当前余额3.43元 前往充值 >
需支付：10.00元
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包
实付元
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明：

1.余额是钱包充值的虚拟货币，按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载，可以购买VIP、付费专栏及课程。

余额充值