算法用途
Sparse Table,又稱ST表,稀疏表。運用倍增的思想,可以解決RMQ,LCA等問題。其優點是線上查詢。預處理複雜度為O(nlogn),查詢複雜度為O(1)。
算法思想
運用倍增的思想,num[i][j]表示區間[i,i+(1 << <script type="math/tex" id="MathJax-Element-1"><<</script>j)]的值。然後進行預處理求出num數組。
算法實作
以求最大值為例:
① 對于預處理,有如下轉移方程式:
num[i][j]=max(num[i][j-1],num[i+(1<<j-1)][j-1]);
這是什麼東西啊??
我們來推一遍:
其實隻是把[i,i+(1 << <script type="math/tex" id="MathJax-Element-2"><<</script>j)]這個區間給分成兩塊,一塊是[i,i+(1 << <script type="math/tex" id="MathJax-Element-3"><<</script>j-1)],另一塊是[i+(1 << <script type="math/tex" id="MathJax-Element-4"><<</script>j-1),i+(1 << <script type="math/tex" id="MathJax-Element-5"><<</script>j)](i+(1 << <script type="math/tex" id="MathJax-Element-6"><<</script>j)==i+(1 << <script type="math/tex" id="MathJax-Element-7"><<</script>j-1)+(1 << <script type="math/tex" id="MathJax-Element-8"><<</script>j-1))。
是以這個區間的最大值就是這兩個區間的最大值的較大者。
然後就推好啦!
② 對于查詢[x,y]之間的最大值,我們可以這樣:
int j=log2(y-x+1);
printf("%d\n",max(num[x][j],num[y-(1<<j)+1][j]));
這又是什麼東西??
我們再來推一遍:
num[x][j]表示[x,x+(1 << <script type="math/tex" id="MathJax-Element-17"><<</script>j)]這段區間,本來是剛好的,但是因為j是向下取整的,是以不一定取得完。取到的區間長度實際為1 << <script type="math/tex" id="MathJax-Element-18"><<</script>j-1。此時我們可以從y-(1 << <script type="math/tex" id="MathJax-Element-19"><<</script>j-1)=y-(1 << <script type="math/tex" id="MathJax-Element-20"><<</script>j)+1這個點開始取(取重了也沒事),取相同的長度。然後在這兩者之間取較大者即可。
模闆
以洛谷P3865 為例:
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define MAXN 150000
using namespace std;
int n,m;
int num[MAXN+][];
inline char readc(){
static char buf[],*l=buf,*r=buf;
if (l==r) r=(l=buf)+fread(buf,,,stdin);
if (l==r) return EOF;
return *l++;
}
int _read(){
int num=; char ch=readc();
while (ch<'0'||ch>'9') ch=readc();
while (ch>='0'&&ch<='9'){ num=num*+ch-; ch=readc(); }
return num;
}
void make(){
for (int i=;i<;i++)
for (int j=;j+(<<i)-<=n;j++)
num[j][i]=max(num[j][i-],num[j+(<<i-)][i-]);
}
int main(){
n=_read(); m=_read();
for (int i=;i<=n;i++)
num[i][]=_read();
make();
for (int i=;i<=m;i++){
int x=_read(),y=_read();
int j=log2(y-x+);
printf("%d\n",max(num[x][j],num[y-(<<j)+][j]));
}
return ;
}
再來個最小值(洛谷P2251):
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define MAXN 1500000
using namespace std;
int num[MAXN+][],q[MAXN+5];
int n,m;
inline char readc(){
static char buf[],*l=buf,*r=buf;
if (l==r) r=(l=buf)+fread(buf,,,stdin);
if (l==r) return EOF;
return *l++;
}
int _read(){
int num=; char ch=readc();
while (ch<'0'||ch>'9') ch=readc();
while (ch>='0'&&ch<='9') { num=num*10+ch-; ch=readc(); }
return num;
}
void make(){
for (int j=;j<=;j++)
for (int i=;i<=n;i++)
num[i][j]=min(num[i][j-],num[i+(<<j-)][j-]);
}
int main(){
n=_read(); m=_read();
for (int i=;i<=n;i++)
num[i][]=_read();
make();
for (int i=;i<=n-m+;i++){
int x=i,y=m+i-;
int j=log2(y-x+);
q[i]=min(num[x][j],num[y-(<<j)+][j]);
}
for (int i=;i<=n-m+;i++)
printf("%d\n",q[i]);
return ;
}