ST表(跳跃表)

最新推荐文章于 2025-04-01 17:42:54 发布
最新推荐文章于 2025-04-01 17:42:54 发布
阅读量258 收藏
点赞数
分类专栏： 数据结构 文章标签： 算法 数据结构 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 1374
P3865 【模板】ST表 题目背景 这是一道ST表经典题——静态区间最大值 请注意最大数据时限只有0.8s，数据强度不低，请务必保证你的每次查询复杂度为O(1) 题目描述 给定一个长度为N的数列，和M次询问，求出每一次询问的区间内数字的最大值。 输入输出格式 输入格式： 第一行包含两个整数N, M 分别表示数列的长度和询问的个数。 第二行包含N个整数（记为 ...
专题三（栈，队列，优先队列，ST表）
hhhh_w_w的博客
02-07 997
栈是一种(Last In, First Out) 的容器适配器，仅支持查询或删除最后一个加入的元素 （栈顶元素），不支持随机访问，且为了保证数据的严格有序性，不支持迭代器。
数据结构值ST表的详细讲解浅显易懂
最新发布
2302_80700357的博客
04-01 502
ST表，即Sparse Table（稀疏表），是一种基于倍增思想的数据结构。它主要用于在**O(1)**时间复杂度内查询给定区间的最值（最大值或最小值）。其原理是通过预处理，利用倍增的思想，将每个区间的最值信息存储起来，以便后续快速查询。
学习笔记——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 949
00 写在前面 平衡二叉搜索树中的RB-tree作为一种效率表现和复杂度很平衡的结构，一直被用作STL set和map的底层支持。 【STL源码剖析】总结笔记（8）：红黑树（RB-tree）探究 【STL源码剖析】总结笔记（9)：set/multiset与map/multimap 而还有一种结构，哈希表（以下称hashtable），在数据具有足够的随机性时，也能够保持在插入删除等操作上的“常数平均时间”表现。也是unordered结构的基础。 hashtable更多的是经验设计 01 概述 hasht
Java 稀疏表是什么
02-28
<think>好的，我现在需要给用户解释Java中的稀疏表是什么。首先，我得确认自己对这个概念的理解是否正确。稀疏表（Sparse Table）是一种数据结构，主要用于处理静态数据的区间查询问题，比如区间最小值、最大值或者最大公约数等。它通过预处理来实现在O(1)或O(log n)时间内回答查询，适用于数据不变的情况。 接下来，我要回忆一下稀疏表的实现原理。它基于动态规划的思想，预处理每个起点开始的长度为2的幂次方的区间，构建一个二维数组。例如，st[i][j]表示从位置i开始，长度为2^j的区间的查询结果。预处理的时间复杂度是O(n log n)，而查询时则将区间分解成两个预处理的区间，取结果，这样可以在O(1)时间内完成，比如RMQ（Range Minimum Query）。 然后，用户提到的是Java中的稀疏表，可能需要给出Java实现的例子。这时候需要考虑如何用Java代码构建稀疏表，比如二维数组的初始化，预处理过程，以及查询方法。需要注意的是Java中数组的操作，比如循环嵌套的顺序，以及位运算的使用。例如，计算区间长度对应的指数k，可以用Math.log或直接位运算找到最高位。 另外，需要说明稀疏表的应用场景和优缺点。比如，适用于静态数据，查询高效，但不支持动态更新。对比其他数据结构，比如线段树，稀疏表的构建更快，但无法处理动态数据。 可能还需要举一个具体的例子，比如求区间最小值，给出具体的代码结构，包括预处理和查询的步骤。同时，注意代码的正确性，比如预处理时的循环边界条件，避免数组越界。 最后，要确保解释清晰，结构合理，用用户容易理解的语言，避免过于专业的术语，必要时举例说明。检查是否有错误，比如时间复杂度是否正确，代码示例是否有语法错误。确保回答符合用户的需求，即了解Java稀疏表的基本概念、实现和应用。</think>稀疏表（Sparse Table）是一种用于高效处理静态区间查询的数据结构，尤其擅长解决**区间最值查询（RMQ）**、**区间GCD查询**等问题。它在Java中的实现核心是通过预处理构建查询表，实现$O(1)$时间复杂度查询。 --- ### 一、核心特点 1. **静态数据**：数据初始化后不再修改 2. **高效查询**：预处理时间$O(n \log n)$，查询时间$O(1)$ 3. **空间效率**：需要$O(n \log n)$存储空间 4. **幂次跳跃**：基于区间长度为$2^k$的预处理 --- ### 二、实现原理 #### 1. 预处理阶段 构建二维数组`st[][]`，其中： $$st[i][k] = \text{区间}[i, i+2^k-1]\text{的查询结果}$$ ```java // Java示例：构建RMQ稀疏表 int[][] buildSparseTable(int[] arr) { int n = arr.length; int k = (int)(Math.log(n) / Math.log(2)) + 1; int[][] st = new int[n][k]; // 初始化长度为1的区间 for(int i=0; i<n; i++) st[i][0] = arr[i]; // 动态规划构建 for(int j=1; (1<<j) <= n; j++) { for(int i=0; i + (1<<j) <= n; i++) { int mid = i + (1 << (j-1)); st[i][j] = Math.min(st[i][j-1], st[mid][j-1]); } } return st; } ``` #### 2. 查询阶段 将任意区间$[L, R]$分解为两个预处理的$2^k$长度区间： $$\text{查询}[L, R] = \text{操作}(st[L][k], st[R-2^k+1][k])$$ ```java // 区间最小值查询示例 int query(int L, int R, int[][] st) { int len = R - L + 1; int k = (int)(Math.log(len) / Math.log(2)); int mid = R - (1 << k) + 1; return Math.min(st[L][k], st[mid][k]); } ``` --- ### 三、应用场景对比 | 数据结构 | 预处理时间 | 查询时间 | 动态更新 | |---------|-----------|---------|---------| | 稀疏表 | $O(n \log n)$ | $O(1)$ | ❌ | | 线段树 | $O(n)$ | $O(\log n)$ | ✔️ | | 前缀和 | $O(n)$ | $O(1)$ | ❌ | --- ### 四、使用注意事项 1. **幂次计算优化**：可用`31 - Integer.numberOfLeadingZeros(len)`替代对数计算 2. **数据类型限制**：适合可重复贡献问题（如min/max/gcd） 3. **区间覆盖验证**：确保分解后的两个区间完全覆盖原区间 4. **空间优化**：对于大数组需注意内存占用 --- ### 五、典型应用示例 ```java public class SparseTableDemo { public static void main(String[] args) { int[] data = {3, 1, 4, 2, 5, 9, 6}; int[][] st = buildSparseTable(data); System.out.println(query(0, 3, st)); // 输出区间[0-3]最小值：1 System.out.println(query(2, 5, st)); // 输出区间[2-5]最小值：2 } // 此处插入上述buildSparseTable()和query()方法 } ``` --- 这种数据结构在算法竞赛和工程中都有广泛应用，特别是需要高频查询但数据静态的场景。理解其原理后，可以灵活扩展到其他符合结合律的区间操作。
评论
添加红包

请填写红包祝福语或标题

个

红包个数最小为10个

元

红包金额最低5元

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

抵扣说明：

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

余额充值