再谈ST表

再谈 ST 表

思想：倍增。

适用范围：对于一个不可修改的序列维护区间最大/最小值询问。

时间：O ( n log ⁡ n ) O(n\log n)O(nlogn)预处理，O ( 1 ) O(1)O(1)查询。

下文以最大值为例。

预处理

状态：设f i , j f_{i,j}fi,j​表示区间[ i , i + 2 j − 1 ] [i,i+2^j-1][i,i+2j−1]的最大值。

那么递推式就有：
f i , j = max ⁡ { f i , j − 1 , f i + 2 j − 1 , j − 1 } f_{i,j}=\max\left\{f_{i,j-1},f_{i+2^{j-1},j-1}\right\}fi,j​=max{fi,j−1​,fi+2j−1,j−1​}
显然边界是f i , 0 = a i f_{i,0}=a_ifi,0​=ai​。其中a i a_iai​是原序列。

图解：

其中第二个，区间右边界是i + 2 j − 1 + 2 j − 1 − 1 = i + 2 j − 1 i+2^{j-1}+2^{j-1}-1=i+2^j-1i+2j−1+2j−1−1=i+2j−1。

查询

假设查询区间为[ l , r ] [l,r][l,r]。

找到max ⁡ { k ∣ 2 k < r − l + 1 ≤ 2 k + 1 } \max\left\{k\mid 2^k<r-l+1\le 2^{k+1}\right\}max{k∣2k<r−l+1≤2k+1}。

把[ l , r ] [l,r][l,r]分解为[ l , l + 2 k − 1 ] ∪ [ r − 2 k + 1 , r ] [l,l+2^k-1]\cup [r-2^k+1,r][l,l+2k−1]∪[r−2k+1,r]。

即从l ll开始的2 k 2^k2k个元素与r rr结尾的2 k 2^k2k个元素。

因为2 k < r − l + 1 ≤ 2 k + 1 2^k<r-l+1\le 2^{k+1}2k<r−l+1≤2k+1，所以这俩区间一定可以覆盖整个查询区间。

对于r − 2 k + 1 r-2^k+1r−2k+1的解释：
r − 2 k + 1 + 2 k − 1 = r r-2^k+1+2^k-1=rr−2k+1+2k−1=r
所以式子就是：
max ⁡ { f l , k , f r − 2 k + 1 , k } \max\left\{f_{l,k},f_{r-2^k+1,k}\right\}max{fl,k​,fr−2k+1,k​}
注意：ST 表是预处理完查询，所以不支持修改。

示例代码

例题：P3865 【模板】ST 表 & RMQ 问题

#include<bits/stdc++.h>usingnamespacestd;typedeflonglongljl;#defineFUP(i,x,y)for(autoi=(x);i<=(y);++i)#defineFDW(i,x,y)for(autoi=(x);i>=(y);--i)inlinevoidRd(auto&num);constintN=1e5+5,L=25;intn,m,a[N];namespaceST{intf[N][L],Lg2[N];voidBuild(){Lg2[1]=0;FUP(i,2,n)Lg2[i]=Lg2[i/2]+1;FUP(i,1,n)f[i][0]=a[i];FUP(j,1,20){FUP(i,1,n){if(i+(1<<(j-1))>n)break;f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);}}return;}intquery(intl,intr){intlens=r-l+1;intk=Lg2[lens];returnmax(f[l][k],f[r-(1<<k)+1][k]);}}intmain(){Rd(n);Rd(m);FUP(i,1,n)Rd(a[i]);ST::Build();intl,r;while(m--){Rd(l);Rd(r);printf("%d\n",ST::query(l,r));}return0;}inlinevoidRd(auto&num){num=0;charch=getchar();boolf=0;while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}while(ch>='0'&&ch<='9'){num=(num<<1)+(num<<3)+(ch-'0');ch=getchar();}if(f)num=-num;return;}