ST表

ST表的数组st[i][k]指从i开始2^k个数里的最值
最直观的用法应该就是求区间最值，即RMQ问题（Range Minimum/Maximum Query）
预处理O(nlogn) 查询O(1)

例题 洛谷P3865 【模板】ST 表
https://www.luogu.com.cn/problem/P3865

#include<iostream>
#include<cmath>
#define forup(i,l,r) for(int i=l;i<=r;i++)
using namespace std;
int n,m;
int st[100100][20];
int lg[100005];
inline int read()
{
	int n=0;
	char m=getchar();
	while(m<'0'||m>'9') m=getchar();
	while(m>='0'&&m<='9')
	{
		n=(n<<1)+(n<<3)+(m^'0');
		m=getchar();
	}
	return n;
} 
int num[100];
inline void write(int a)
{
	int len=0;
	do num[len++]=a%10; while(a/=10);
	while(len--) putchar(num[len]+'0');
}
void ST()
{
	forup(i,1,n)
	{
		st[i][0]=read();
	}
	int p=lg[n];
	forup(k,1,p)
	{
		forup(i,1,n-(1<<k)+1)
		{
			st[i][k]=max(st[i][k-1],st[i+(1<<(k-1))][k-1]);//i开始的2^k个中的最大值等于i开始2^(k-1)的最值a1和i+2^(k-1)开始2^(k-1)的最值a2的较大者 
			//<<优先级比+-低，要加括号 
		}
	}
}
inline int query(int l,int r)
{
	int p=lg[r-l+1];//找到p满足2^p<len且2^p+2^p>=len 
	return max(st[l][p],st[r-(1<<p)+1][p]);//从l开始往后2^p和从r开始往前2^p，两者的并集就是[l,r]，也是因此2^p<len 
	//<<优先级比+-低，要加括号 
}
void lg_init()
{
	forup(i,2,n) lg[i]=lg[i>>1]+1;
}
int main()
{	

	cin>>n>>m;
	lg_init();//初始化lg数组 
	ST();//建st表 
	int l,r;
	forup(i,1,m)
	{
		l=read(),r=read();
		int p=lg[r-l+1]; 
		write(query(l,r)); putchar('\n');
	}
	return 0;
 } 

有几个点，
一是<<和>>的优先级是比+-低的，所以要额外加括号；
二是关于lg数组是用来提高效率的，用log2也没什么不可；
另外之前了解到的递推式是下面这个
lg[i]=lg[i-1]+((1<<(lg[i-1]+1))==i);
显然，还是现在这个更简洁也快理解也比较容易

参考：https://blog.csdn.net/m0_46201544/article/details/125270545
运算符优先级：https://blog.csdn.net/nicky_zs/article/details/4053146