title: ST表
date: 2022-11-17 16:07:25
tags: 算法
本文章遵守知识共享协议 CC-BY-NC-SA ，转载时需要署名，推荐在我的个人博客阅读。
大意
ST 表是一种静态数据结构，用于快速查询区间RMQ 问题。
前置知识：
- 位运算
讲解
数据结构
ST 表的结构如下
若原数据如下：
| 1 | 2 | 3 | 4 | 5 |
|---|
则 ST 表（最大值）应该是
| 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 |
| 2 | 3 | 4 | 5 | -1 |
| 4 | 5 | -1 | -1 | -1 |
很懵吗？其实仔细观察，第 $j$ 行第 $i$ 列的值维护的是一个区间 $[i,i+2^{j-1})$ 中的最大/最小值。
那它应该如何知道一段区间呢？很简单，只需要将两个重叠区间再次求值就行，正是因为这一点，ST表只能用于可重复贡献问题。
有关可重复贡献问题
其实很简单，若一个值被重复参与贡献答案还不影响答案，则这是个可重复贡献问题。
举个例子， 求区间中的 $ max $ 是可重复贡献问题，而求区间和则不是。
因为 $ \max(a,b,b,b,b,b,b,b,b,b,b,b,b,b,b,b,b,b) $ 和 $ \max(a,b) $ 产生的结果是一样的，而 $a+b+b$ 在 $b$ 不等于 $0$ 时显然不等于 $b$ 。
构造
根据上文我们知道，第 $j$ 行第 $i$ 列的值维护的是一个区间 $[i,i+2^{j-1})$ 中的最大/最小值。
所以，要得到当前区间的最大/最小值，需要两个区间参与运算。
可以得到状态转移方程为 $ST_{i,j}=\max(ST_{i-1,j},ST_{i-1,j+2^{i-1}});$
for(register int i=1;i<log2(n)+1;i++)
for(register int j=0;j<n;j++)
ST[j][i]=max(ST[j][i-1],ST[j+(1<<(i-1))][i-1]);
查询
在构造ST表后，肯定会查询区间最大/小值（这不是废话吗）。
首先可以知道要互相覆盖的两个区间长度应该为 $ 2^{\log{r-l+1}} $ (这是在ST表中小于等于当前区间的最长长度)
然后分别构造出另外两个区间 $ [l,l+2^{length}] $ 和 $ [r-2^{length}+1,r] $，在ST表中对应的区间是 $ ST_{l,length} $ 和 $ ST_{r-2^{length}+1,length} $
len=lgg[r-l+1];
tppp=max(sttable[l][len],sttable[r-(1<<len)+1][len]);
P3865-【模板】ST 表
纯粹的模板题目，应该不用说。
P8818-[CSP-S 2022] 策略游戏
多开几个ST表。
原文地址：http://www.cnblogs.com/rickyxrc/p/16911022.html
