稀疏表ST表算法NOICSP

稀疏表ST表算法NOICSP_SACM_ICPCST表（SparseTable）算法ST表名稀疏表，常用來(lái)處理區(qū)間最值查詢。是一種離線算法，即不可以邊更改邊查詢。ST表用到了倍增思想。ST表預(yù)處理時(shí)間O(NlogN)，單次查詢時(shí)間復(fù)雜度為O(1)，總時(shí)間復(fù)雜度O(Nlog（n+m）)。RMQ問題RMQ問題即區(qū)間查詢問題，是指對(duì)于長(zhǎng)度為n的數(shù)列a[]，更改或查詢數(shù)列a[]中下標(biāo)在[i,j]區(qū)間內(nèi)的值。如果查詢的是最大值或最小值，一般可以用ST表算法解決。需要強(qiáng)調(diào)，ST算法只適用于靜態(tài)區(qū)間求最值。如果是動(dòng)態(tài)的，還是使用線段樹。一維ST表ST算法是基于倍增思想設(shè)計(jì)的算法。ST算法記錄從每個(gè)元素開始的連續(xù)長(zhǎng)度為2^k的區(qū)間中元素的最大值或最小值。類似于動(dòng)態(tài)規(guī)劃，規(guī)定f[i,j]表示從第i個(gè)元素起連續(xù)2^j個(gè)數(shù)中的最大值或最小值，即記錄區(qū)間[i,i+2^j-1]中元素中的最大值或最小值。由定義可知，f[i,j]一定包含偶數(shù)個(gè)數(shù)字，故把f[i,j]平均分成兩段，從i到i+2^{j-1}-1為一段，i+2^{j-1}到i+2^j-1為另一段，長(zhǎng)度均為2^{j-1}。如下圖：于是得到狀態(tài)轉(zhuǎn)移方程為：f[i,j]=max{f[i,j?1],f[i+2^(j?1),j?1]}，其中f[i,0]=a[i]。初始化代碼如下：對(duì)于一個(gè)查詢區(qū)間[l,r]，只要找到一個(gè)或者多個(gè)2的整數(shù)倍長(zhǎng)度的區(qū)間覆蓋[l,r]，然后取這些區(qū)間最大值的最大值就是答案了，最小值同理。把[l,r]覆蓋完整的一種辦法是把區(qū)間的長(zhǎng)度按照二進(jìn)制分成多個(gè)2的整數(shù)倍區(qū)間，顯然這些區(qū)間是不重疊的。不重疊的要求造成這種分割增加了算法常數(shù)，一次查詢可能就要求幾十次最大值。另一種方法為了減少分割出的區(qū)間數(shù)量，允許區(qū)間重疊，這樣所有的情況下最多只要兩個(gè)區(qū)間就好了，見下圖所示：假設(shè)要求區(qū)間[l,r]中序列a[]的最大值，找到一個(gè)數(shù)k滿足2^k<r-l+1,即k=log(r-l+1)/log(2)，此公式為對(duì)數(shù)換底公式。這樣，可以把這個(gè)區(qū)間分成兩個(gè)部分：[l,l+2^k-1]和[r-2^k+1,r]。這兩個(gè)區(qū)間恰好是剛剛已經(jīng)初始化好的，前者對(duì)應(yīng)的是f[l,k]，后者對(duì)應(yīng)的是f[r-2^k+1,k]。這樣，只要看這兩個(gè)區(qū)間的最大值或最小值，就可以知道整個(gè)區(qū)間的最大值。這個(gè)算法的高明之處不是在于動(dòng)態(tài)規(guī)劃的建立，而是它的查詢，它的查詢效率是O(1)。例題：ST表模板給定一個(gè)長(zhǎng)度為N的數(shù)列，和M次詢問，求出每一次詢問的區(qū)間內(nèi)數(shù)字的最大值。輸入第一行包含兩個(gè)整數(shù)N,M，分別表示數(shù)列的長(zhǎng)度和詢問的個(gè)數(shù)。第二行包含N個(gè)整數(shù)，依次表示數(shù)列的第i項(xiàng)。接下來(lái)M行，每行包含兩個(gè)整數(shù)，表示查詢的區(qū)間。輸出包含M行，每行一個(gè)整數(shù)，依次表示每一次詢問的結(jié)果。例題：求區(qū)間內(nèi)最小值一個(gè)含有n項(xiàng)的數(shù)列，求出每一項(xiàng)前的m個(gè)數(shù)到它這個(gè)區(qū)間內(nèi)的最小值。若前面的數(shù)不足m項(xiàng)則從第1個(gè)數(shù)開始，若前面沒有數(shù)則輸出0。輸入第一行兩個(gè)整數(shù)，分別表示n，m。第二行，n個(gè)正整數(shù)，為所給定的數(shù)列ai。輸出一行n個(gè)整數(shù)，第i個(gè)數(shù)為序列中ai之前m個(gè)數(shù)的最小值。此題與上題相類，樣例及代碼略。ST表小結(jié)ST表在信息學(xué)競(jìng)賽中獨(dú)立使用的情況很少見。特別是在高級(jí)別比賽中更是很難見到直接考