倍增与ST表

几辈子不复习都忘了

ST 表是用于解决 可重复贡献问题 的数据结构。 ——https://oi-wiki.org/ds/sparse-table/

可重复贡献问题(RMQ 问题)

定义一种运算 $\text{op}$，满足：

$$x \ \text{op} \ x = x$$

推广到区间，设

$$a_{[l,r]} = a_l \ \text{op} \ a_{l+1} \ \text{op} \ \dots \ \text{op} \ a_r$$

考虑两个相交的区间 $[l_1,r_1]$、$[l_2,r_2]$，它们的交集为 $[l_2,r_1]$。则有：

$$a_{[l_1,r_1]} \ \text{op} \ a_{[l_2,r_2]}$$

展开为：

$$= a_{[l_1,l_2)} \ \text{op} \ a_{[l_2,r_1]} \ \text{op} \ a_{[l_2,r_1]} \ \text{op} \ a_{(r_1,r_2]}$$

利用运算的性质 $x \ \text{op} \ x = x$：

$$= a_{[l_1,l_2)} \ \text{op} \ a_{[l_2,r_1]} \ \text{op} \ a_{(r_1,r_2]}$$

最终得到：

$$= a_{[l_1,r_2]}$$

--From https://blog.csdn.net/UnderTheTime/article/details/136631866

我们设 $f\left[ i \right] \left[ j \right] \text{表示区间}\left[ i,i+2^j-1 \right] \text{的最大值}$

ST表不仅仅用于区间最大值,这里只是方便理解

查询

假设我们已经初始化完了,如果想要查询可以直接查 $\left[ l,l+2^x \right] ,\left[ r-2^x-1,r \right] $ 的最大值然后对比哪个区间的最大值最大
其中 $2^x$ 是 $\lfloor \log _2\left( r-l+1 \right) \rfloor $ ,即求最大的整数 $x$，使得 $2^x \leq (r-l+1)$

具体查询表达应该是
$$\mathrm{ans}=\max \left( f[l][k]\;,\;f[r-2^k+1][k] \right) ,\quad k=\lfloor \log _2(r-l+1) \rfloor $$
至于为什么,参考折叠内容

预处理

已经构想了如何查询,接下来研究如何预处理

ST表预处理

依靠动态规划的思想,我们能想到这样转移

$$f\left[ i \right] \left[ j \right] =\max \left( f\left[ i \right] \left[ j-1 \right] ,f\left[ i+2^{j-1} \right] \left[ j-1 \right] \right) $$

$$即\max\mathrm{[}i,\,i+2^j-1]=\max \bigl( \,[i,\,i+2^{j-1}-1],\;[i+2^{j-1},\,i+2^{j-1}+2^{j-1}-1]\, \bigr)
\\
\text{合并同类项,得}:\max\mathrm{[}i,\,i+2^j-1]=\max \bigl( \,[i,\,i+2^{j-1}-1],\;[i+2^{j-1},\,i+2^j-1]\, \bigr) $$

只要先枚举 $j$,再枚举 $i$ ,就可以保证 $f\left[ i \right] \left[ j-1 \right] ,f\left[ i+2^{j-1} \right] \left[ j-1 \right] $ 都是上一轮处理过的

$\log _2$数组预处理

因为log2是保留字,所以我们使用lg2作为变量名

我们的目的是快速预处理 $\lg 2\left[ x \right] =\lfloor \log _2x \rfloor $

因为 $$\lfloor \log_2i \rfloor =\lfloor \log_2\lfloor \frac{i}{2} \rfloor \rfloor +1$$

所以可以使用位运算和递推快速进行计算

即

for(int i=2;i<=n;i++)lg2[i]=lg2[i>>1]+1;

完整实现

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
int f[MAXN][20],lg2[MAXN];
//f[n][20]中的20表示最大长度2^20
//log2为保留字,使用lg2
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>f[i][0];//区间[i,i]的最大值是自己
    //预处理log2
    lg2[1]=0;
    for(int i=2;i<=n;i++)lg2[i]=lg2[i>>1]+1;
    
    //ST表初始化
    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 q;//q次问答
    cin>>q;
    while(q--){
        int L,R;
        cin>>L>>R;
        int k=lg2[R-L+1];//计算出最大的2^k
        cout<<max(f[L][k],f[R-(1<<k)+1][k])<<"\n";
    }
}