ST表学习笔记(未完)

安卿

2025-06-07 11:36:29

发布于：上海

6阅读

0回复

0点赞

观前说明:作者菜无条件接受所有正常建议轻喷
写作目的:发现ACGO好像没有较为详细地有关ST表的文章最近刚好在学觉得写这个帮助清晰思路就写了
注释:本文有参考xiaoshumiao(洛谷)的ST表,天泽龟(洛谷)的P3865 【模板】ST 表 && RMQ 问题题解和进阶算法思想(洛谷课程)
前置:
1.小学语文,数学知识(不提供讲解):
如: $2^{2^i}$ = $2^{2*2^{i-1}}$

2.二进制分解思想:
以2020 CSP-J T1:优秀的拆分为例:
$8$ = $2^3$
$8$ 的二进制:1000
$18=2^1+2^4$
$18$ 的二进制:10010

正文开始:
1.应用:用于快速求出区间内最小/最大值的数据结构

2.思想:利用倍增思想(来缩短时间)

倍增思想:
倍增是基于二进制分解思想的预处理算法.
*二进制分解思想:具体参考2020 CSP-J T1:优秀的拆分
倍增主要用于优化树结构中的跳跃路径查询问题
操作方式:记录每个节点向上跳跃 $2^j$ 层的祖先节点

而在ST表中,倍增思想的体现在于其数组的定义

似乎比较难懂.可以再看这题倍增快速幂
这道题主要是求 $a^b$ :
b使用二进制拆分:b= $b_0+b_1+b_2...+b_n$
*这里的每一个 $b_i$ 都已二次方形式表现也就是 $2^i$
由此,最后需要求的 $a^b$ 变成:
$a^{b_0}*a^{b_1}*a^{b_2}*...*a^{b_n}$
设 $f(i)$ 为 $a^{2^{i}}$ 也可以转变为 $a^{2*2^{i-1}}$ 也就是 $f(i-1)^2$ (回收开头之小学数学知识)
那么,需要转换的 $a^b$ 变成:
$f(i_0)*f(i_1)*f(i_2)*f(i_3)*......f(i_n)$
*这里的 $i_0,i_1,i_2,i_3$ 等没有特定的数值.它们的数值取决于 $b_0,b_1,b_2,b_3$ 是多少:
$i_x$ = $log_2(b_x)$
~~似乎更难懂了~~
代入几个数值:
a=3 , b=5
b= $2^0+2^2$
$3^{5}$ = $3^{2^{0}}*3^{2^{2}}$
$3^{5}$ = $f(0)+f(2)$
$f(0)=3^{2^0}=3^1=3$
$f(1)=f(0)^2=3*3=9$
$f(2)=f(1)^2=9*9=81$
$3^5=3*81=243$
此次代入数值的成果:
1.理清思路
2.明白需要初始化: $f(0)$ 不可能从 $f(-1)$ 来
3.明白 $f(i)$ 并不是连续的,但是从 $i_0$ 到 $i_n$ 的每一个 $f(i_x)$ 都需要求出,尽管它们中有一部分不需要(但为了求它们的后续值,依然需要将它们求出)
丑陋代码:

#include<bits/stdc++.h>
using namespace std;
int main(){
	long long a,b,q;
	cin>>a>>b>>q;
	int na=a;
	int nb=b;
	long long answer=1;
	int shu=0;
	long long sum=0;
	while(1){
		if(b==0)break;
		if(shu==0){
			sum=a;
		}else sum=sum*sum%q;
		if(b%2==1){
			answer*=sum;
			answer%=q;
		}
		shu++;
		b/=2;
	}
	cout<<na<<"^"<<nb<<" "<<"mod"<<" "<<q<<"="<<answer;
	return 0;
}

然后,可以观察一下本题的时间复杂度:如果说,直接乘b次a的话,时间复杂度是 $O(b)$ 但是(似乎是)使用了倍增后,它的时间复杂度降到了 $O(log n)$

3.实现:(此处从P3865 【模板】ST 表 && RMQ 问题入手)
这道题分为两个阶段:预处理阶段&求最值阶段

一.预处理阶段
这里的"预处理"指的是使用一个二维数组f,存储所有区间的最值.
$f_{i,p}$ 表示以p为左端点,长度为 $2^i$ 的区间的最大值.(回收上文倍增思想的体现)
考虑 $2^i$ = $2^{2*2^{i-1}}$ 这个式子(回收开头).长度为 $2^i$ 的区间可拆成两个长度为 $2^{i-1}$ 次方的小区间.
第一个区间的端点为p,第二个区间的端点为 $p+2^{i-1}$ .
递推式: $f_{i,p}=max(f_{i-1,p},f_{i-1,p+2^{i-1}})$

有帮助，赞一个

去预览

0/2000

这里空空如也

热门讨论