[洛谷P3865] ST表

洛谷P3865

ST表——RMQ問題

RMQ問題:

RMQ問題就是指求區間最值的問題。

這裡的解決方法采用ST表

思想：

首先先回顧一下線段樹的想法，将一個數列不斷二分，并記錄目前管轄區間内的最值。

但線段樹查詢操作并不是O(1)，是以面對大量查詢操作會t

因為線段樹會把大區間劃分成很多個不會重合的小區間，是以會耗時

而如果我們能将這個大區間直接劃分成兩個區間，直接用max求得，不是就會快很多了嗎。

e.g. f[1,5]記錄1-5之間的最值，f[4,8]記錄5-8最值

是以求[1,8]最值就直接max(f[1,5],f[4,8]);

而我們采用倍增的思想的話，可以直接将一個大區間化分成兩個可能重合的兩個小區間

求f[n,m]，可以直接求兩個區間的max，達到了O(1)的效果。

什麼是倍增的思想? 顧名思義，就是不斷翻倍1–>2,2–>4,4–>8

ST表便是讓我們能知道每個點之後的 1個長度的最值，2的長度的最值，4個長度的最值,n^2的長度的最值

完美的情況來說，剛好可以把一個大區間分成兩個不重合的小區間

記: f數組存區間最值

藍色為(1,n)的f數組

而綠色是為: 若求 下一層區間最值 所需的另一個區間

比如求(1,8),你已經求得(1,4)的最值，隻需要知道個(5,8)的最值，再max兩個區間便可求得

會發現在 求f(5) 長度為4的區間最值時，會把f(5,8)求出來

求f(9) 長度為8的時候，會把f(9,16)求出來

即一個區間(n,m)恰好可以分為(n,2^k) (2^k +1,m) (k∈Z) 的兩個區間

為什麼會這樣呢?【白學打死x……】

因為倍增既是二分的反操作，是以可以恰好把一個區間分成兩區間

當然不完美的情況，即有重合的情況【即無法将一個區間(n,m)恰好分成(n,2^k) (2^k +1,m)的情況

我們仍可以把這個區間，分成一個(n,k1)(k1< m, k1為n+2^k) 和(k2,m)(k2> n, k2為m-2^k +1)

如上圖，可以把(1,6)分為(1,4[2^2])和(3[6-2^2 +1],6)

是以我們建立一個表，存所有倍增劃分出來的區間最值，這裡便是離線預處理

回答就直接以玄學操作查表并回答

大概的操作便是這樣

實作

建立ST表

注意到: 以上講的都是正着倍增的操作，即1找(1,1)(1,2)(1,4)(1,8)…(1,2^k)的最值

然後2找(2,2)(2,3)(2,4)(2,6)…

但個人寫的是倒着倍增的，即1隻找(1,1)的最值

2為(2,2)(2,1);3為(3,3)(3,2)(3,1);4為(4,4)(4,3),(4,2),(4,0)的最值

以下都是按倒着倍增來講的

我們定義個ST表,ST[N][log2N]

ST[i][j]表示第i個數開始， 前面長度為2^j的最值

e.g.ST[13][3]便是(6[13-2^3 +1],13)的最值。【這裡+1因為是長度為8，是以6到13長度才為8

至于為什麼第二位定位log2N，因為每次倍增的話2^n到N,是以隻需定義到log2N

是以易知，所有ST[i][0]便是其本身(ST[i][0]為長度為1範圍的最值是以就是本身啦

之後開始正式求ST表了

我們會發現，ST[i][j]=max(ST[i][j-1],ST[i- 2^(j-1)][j-1]) 【這裡看不懂先别急後面解釋【因為我也很讨厭什麼說一大堆無關的然後「我們易得：kjaf89&*^834ho18ikG90)93」就把結論說出來了明明完全看不懂呀_(:зゝ∠)_……

e.g.ST[13][3]求(6,13)的最值，便可從(6,9)(10,13)這兩個區間中求出，便剛好為ST[13][2](10[9- 2^2 +1],13)和ST[9 (13- 2^2) ][2](6,9)當中求得

因為ST[i][j]表示i開始前面2^j長度的最值

2^j=2^(j-1)+2^(j-1)，即長度為2^j的區間恰好可以分為兩個2^(j-1)的區間

便可以Dp的思想，将ST表求出來

代碼如下：

void Init()
{
    for (int i=; i<=n; i++) F[i][]=Num[i];    //剛開始f[n][0],即長度為1的序列中最小的就是它本身。
    //從2開始用Dp求 
    for (int i=; i<=n; i++)
    { 
        F[i][]=Work(F[i][],F[i-][]);    //這裡特殊處理個[i][1]，因為2^(1-1)=1,而2<<(1-1)=2, 
        for (int j=; j<=Log[i]; j++)
/*
這裡自己提前打了個Log表，從來存 這個數最大能存到前面 幾個2^k長度 e.g.log2=1;log3=1;log4=2;log5=2;log6=2;log7=2;log8=3;log9=3
3隻能存到(2,3),4隻能存到(1,4)[長度為4<---2^log[4] ], 9隻能存到(2,9)[長度為8<---2^log[9]
*/
        F[i][j]=Work(F[i][j-],F[i- (<<(j-))][j-]);  //Dp操作前面已解釋
    }
}
           

這裡出現了一個Log表，作用已在代碼中解釋了，那麼如何求出這個Log表呢[以下均用log代替log2

void InitLog()  //初始化Log數組 
{
    Log[]=,Log[]=;
    for (int i=; i<=n; i++) Log[i]=Log[i/]+;
}
           

其實就這麼簡單幾句，因為 logx=logx−log2+1=log(x2)+1

查詢ST表

我們已經将所有區間都分成了2^k，根據前面的思路，怎麼剛好把這個(l,r)區間拆成(l,l+2^k-1)與(r-2^k,r)這樣的兩個區間呢?

正确的操作:

這裡必定有且僅有一個k使分成的兩個區間為兩個可能重合的小區間

如果k小1或大1必定會成為下面這兩種區間【這裡自己想一下吧很好了解orz……

窒息的操作:

嗦了這麼多，k到底怎麼找呢?……

既要滿足

l<=r−2k<=l+2k−1<=r

【可看上圖了解……

會易得 k=Log[r-l+1]

e.g. (2,7),k=Log[6]=2; 驗證: (2,5)(4,8)剛好滿足

因為r-l+1 代表是這個區間的長度,∴區間一半長度<=2^k<=區間長度，

然後balabala帶到公式裡會發現這樣才剛好成立【其實是你懶得證吧x……【提示了這麼多自己應該會證了吧233……

求出k過後，再看上圖，應該不難了解直接return max(F[l+2^k-1][k],F[r][k])了吧……

【l+2^k -1的-1不懂的話自己啃啃吧qwq懶癌又犯了……

代碼如下:

int Find(int l, int r)
{
    int k=Log[r-l+];   //當這裡查詢的時候，我們将這個區間化為兩個存在于我們ST表的區間，而這裡即看(l,l+2^k)∪(l+2^k+1,r)=(l,r),發現k求解=log2(r-l+1) 
    return Work(F[l+(<<k)-][k],F[r][k]);
}
           

最後Ac代碼:

#include<bits/stdc++.h>
#define N 100005
#define Work max
int Log[N],Num[N],F[N][],n;
using namespace std;
inline int Read()
{
    int f=,num=;
    char t=getchar();
    while (t<'0' || t>'9') if (t=='-') f=-,t=getchar(); else t=getchar();
    while (t>='0' && t<='9') num=num*+t-'0',t=getchar();
    return f*num;
}
void InitLog()  //初始化Log數組 
{
    Log[]=,Log[]=;
    for (int i=; i<=n; i++) Log[i]=Log[i/]+;
}
void Init()
{
    InitLog();
    for (int i=; i<=n; i++) F[i][]=Num[i];    //剛開始f[n][0],即長度為1的序列中最小的就是它本身。
    //2開始，log2=1;log3=1;log4=2;log5=2;log6=2;log7=2;log8=3; 
    for (int i=; i<=n; i++)
    { 
        F[i][]=Work(F[i][],F[i-][]);//這裡特殊處理個1，因為2^(1-1)=1,而2<<(1-1)=2, 
        for (int j=; j<=Log[i]; j++) 
        F[i][j]=Work(F[i][j-],F[i- (<<(j-))][j-]);
    }
}
int Find(int l, int r)
{
    //if (l==r) return Num[l]; //這裡l==r的時候直接特判【實際上是因為會求解出來k=0造成1<<k=1,即2^k=0出錯…… //後面發現完全不用自己當時阿庫娅了……//雖然也不知道為啥但是debug看出來的确不用orz……
    int k=Log[r-l+];   //當這裡查詢的時候，我們将這個區間化為兩個存在于我們ST表的區間，而這裡即看(l,l+2^k)∪(l+2^k+1,r)=(l,r),發現k求解=log2(r-l+1) 
    return Work(F[l+(<<k)-][k],F[r][k]);
}
void Test() //輸出測試資料而已懶得删_(:зゝ∠)_……
{
    for (int i=; i<=n; i++)
    {
        cout<<"N is: "<<i<<endl; 
        for (int j=; j<=Log[i]; j++) cout<<F[i][j]<<" ";
        cout<<endl;
    }
}
int main()
{
    int q,l,r;
    n=Read(),q=Read();
    for (int i=; i<=n; i++) Num[i]=Read();
    Init();
    //Test();
    while (q--)
    {
        l=Read(),r=Read();
        printf("%d\n",Find(l,r));
    }
}
           

最後祝您，身體健康題題Ac，再見……