程式員必須會的基本算法5-ST稀疏表處理RMQ問題

ST(稀疏表):

​​

​Sparse Table is a data structure that answers static Range Minimum Query (RMQ). It is recognized for its relatively fast query and short implementation compared to other data structures.​

​​ 它是對于靜态資料快速查詢任意區間最值問題的一種資料結構,資料是靜态的,不能修改.

ST一般處理兩種問題:

RMQ(Range Minimum Query)問題(區間最值問題):
預處理時間複雜度O(nlog(n)), 查詢時間複雜度:O(1)
RMQ問題也可以使用線段樹來解決(資料可以是動态的):
預處理時間複雜度:O(nlog(n)),查詢時間複雜度:O(log(n))      

RGQ(Range Gcd Query)問題(區間最大公約數問題)      

ST表使用的情景:

RMQ問題,一般暴力的求一個區間的最值問題,時間複雜度是O(n),單次的查詢還可以接受,但是多次需要查詢不同的區間的最值,在這個查詢裡面就要消耗O(n)的時間複雜度,有時候是不能接受的,比如在競賽裡面,那麼就是使用ST表了,ST表查詢區間的最值的時間複雜度是O(1)

哈哈,前面說了這麼多,都是說它有多好,下面正式進入主題,以一個例子說一下

我們有一個資料: 3 1 2 5 4 ,将它放在數組arr中

現在我們需要查詢出這個資料的任意一個區間的最大值,使用ST算法進行解決

我們先構造一個ST表,就是一個二維數組,數組的大小為[n][log(n)],n是資料的個數

結果如下圖所示

解釋一下ST表的含義,s[i][j]代表的是從第i個資料開始,2 ^ j個數字的區間中的最大值,就是數組arr的[i,i+2 ^ j-1]區間的最大值,

根據表的規律,可以得出​

​ST表的初始化公式:s[i][j]=max(s[i][j-1],s[i+1<<(j-1)][j-1])​

​ 這個公式也好了解,ST表的行i表示從第i個數開始的區間,列j表示這個區間裡面有2 ^ j個數,

要求s[i][j]的值,就是區間[i,i+2 ^ j] 的最大值,

這個區間的最大值不就是 s[ i ][ j-1] (區間[i,i+2 ^ (j-1) -1] 最大值)和

s[i+1<<(j-1)][j-1] (區間[i+2 ^(j-1), i+ 2 ^ j -1]最大值) 這兩個數中最大的一個嗎?

就是将這個大的區間分成兩個小區間的,得到兩個小區間的最大值,再在兩個值中選擇最大的那個,就是這段區間的最大值了

是以ST表後面的狀态是繼承前面的狀态的

對于上面的指數呀,還有log這個函數呀,log是以2為底的(需要轉化),這兩種資料可以使用這這種方法生成
    int[] a=new int[30];
    a[0]=1;
    for(int x=1;x<a.length;x++)
    {
      a[x]=a[x-1]*2;
    }
    int[] log=new int[30];
    log[0]=-1;
    for(int x=1;x<log.length;x++)
    {
      log[x]=log[x/2]+1;
    }
    System.out.println(Arrays.toString(a));
    System.out.println(Arrays.toString(log));      

前面都是預處理,将ST建立好後,接下來就是查詢區間的最大值

我先給出查詢的公式再解釋

len=(int)(Math.log(right-left+1)/Math.log(2))
最大值=max( s[left][len] , s[right-(1<<len)+1][len])      

這個公式應該怎麼了解呢?這樣的,先明确一下我們的目的,求這個區間的最大值,現在假設是求這五個資料的最大值,我們又要是使用ST表的,但是ST表沒有直接存儲從第一個元素開始,第五個元素結束的最大值,ST表存儲的都是2的次方個資料的區間的最大值

那麼我們就想将這個區間分成兩部分,而且是兩部分的區間的最大值能在ST表裡面找到最大值,(這兩個區間可能重疊,也可能不重疊,像現在的例子就重疊了)

那現在的問題就是我們要怎麼分

我們發現,2 ^ (int)(log(len)) 的值是在len/2到len之間的(這裡的len隻是表示一個數)

因為 2 ^(log(len)就是len,但是 (int)(log(len)就是将小數點去除了,

但是2 ^ (int)(log(len)) 肯定比len/2大,因為len/2是(log(len)少了一個1