ST表(跳跃表)

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 lr之间的数的最大值是多少

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+2j1]区间的最大长度,ii+2j12j个数字递推边界F[i,0]=A[i],根据公式F[i][j]=max(F[i][j1],f[i+2j1)][j1])询问时找出小于区间长度下最大的K次幂,因为F[l][k],F[r2k+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;
}
<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、付费专栏及课程。

余额充值