ST表入门

FammerJohn

于 2024-12-23 21:34:26 发布

阅读量884

点赞数 19

分类专栏：算法文章标签：算法

本文链接：https://blog.csdn.net/wrnxrxsb/article/details/144677831

版权

算法专栏收录该内容

7 篇文章

订阅专栏

ST表简介

$ST$ 表 $（ Sp a rse T ab l e ，$ 稀疏表 $）$ 是一种用于高效处理区间查询的数据结构，主要用于解决可重复贡献问题，如区间最大值、最小值、最大公约数等。

$ST$ 表的核心思想是利用倍增的思想，通过预处理来快速计算出各个区间的最值。

如何构建和查询 $ST$ 表

构建 $ST$ 表：

初始化：

当区间长度为 $1$ 时，即 $f_{i,0}$ ，其值为数组中对应的元素 $a_i$ 。

code

for(int i=1; i<=n; i++)
{
	f[i][0] = f1[i][0] = a[i];
}

状态态转移方程：

$f_{ij} = max(f_{i,j-1}, f_{i+2^(j-1),j-1})$ ，即将长度为 $2^j$ 的区间分成两个长度为 $2^{(j-1)}$ 的区间，取这两个区间的最大值。

code （以最大值为例）

for(int j=1; (1<<j) <=n; j++)
{
	for(int i=1; i+(1<<j-1) <=n; i++)
	{
		f[i][j] = max(f[i][j-1] , f[i+(1<<j-1)][j-1]);
	}
}

查询ST表：

对于查询区间 $[l, r]$ ，首先计算出一个整数 $k$ ，使得 $2^k$ 尽可能接近但不超过 $r - l + 1$ ，即 $k = log_2(r-l+1)$ 。然后查询两个子区间 $l, l+2^k-1]$ 和 $r-2^k+1, r]$ 的最大值，即 $max(l, r) = max(f_{l,k}, f_{r-2^k+1,k})$ 。

code


int ansmax (int l, int r)
{
	
	int k = Log[r - l + 1];
	return max (f[l][k] , f[r-(1<<k)+1][k]);
}

完整代码

#include<iostream>
#include<cstdio>
#include<cmath>
const int N = 1e5+5;
using namespace std;
int n,k,f[N][25],a[N],Log[N];


void init()
{
	Log[1] = 0;
	for(int i=2; i<=n+1; i++) Log[i] = Log[i/2] + 1;
	for(int i=1; i<=n; i++)
	{
		f[i][0] = f1[i][0] = a[i];
	}
	for(int j=1; (1<<j) <=n; j++)
	{
		for(int i=1; i+(1<<j-1) <=n; i++)
		{
			f[i][j] = max(f[i][j-1] , f[i+(1<<j-1)][j-1]);
		}
	}
}

int ansmax (int l, int r)
{
	
	int k = Log[r - l + 1];
	return max (f[l][k] , f[r-(1<<k)+1][k]);
}

int main()
{

	return 0;
}