01 故事起源

有N個(gè)數(shù)排列成一排，給定一個(gè)區(qū)間，如何快速找出區(qū)間內(nèi)最大的數(shù)是多少呢？

02 分析

首先想到的自然是從區(qū)間頭開(kāi)始，依次遍歷完區(qū)間內(nèi)的元素，這樣就可以找出結(jié)果了。但這個(gè)復(fù)雜度是O（n），肯定不是我們想要的。

再來(lái)分析一下有什么特點(diǎn)呢？

這些數(shù)不會(huì)更改，所以每個(gè)區(qū)間的結(jié)果是不會(huì)變的，是否可以把所有的區(qū)間結(jié)果先計(jì)算出來(lái)？

如果數(shù)據(jù)規(guī)模很小確實(shí)可以，一旦數(shù)據(jù)過(guò)大肯定就不行了，因?yàn)闀r(shí)間和空間都是O（n^2）。

再考慮一下，區(qū)間的最值是有很強(qiáng)的傳遞關(guān)系，這就引導(dǎo)我們可以把大問(wèn)題化為小問(wèn)題。

很顯然，這就是一個(gè)標(biāo)準(zhǔn)的線段樹(shù)模型，不過(guò)今天我們?cè)贀Q一個(gè)更加高效的算法，稀疏表。 03 稀疏表稀疏表的思想就是提前預(yù)處理數(shù)據(jù)，所以主要針對(duì)數(shù)據(jù)不變的情況，而線段樹(shù)更加靈活，可以動(dòng)態(tài)維護(hù)數(shù)據(jù)的變化。

首先還是將區(qū)間劃分成很多的小區(qū)間。那如何劃分更合理？

第2章節(jié)中，我們枚舉了所有的區(qū)間情況，可以看出其實(shí)有很多重復(fù)的情況，比如下面［0，3］其實(shí)可以通過(guò)［0，1］和［2，3］組合出來(lái)。

可以根據(jù)長(zhǎng)度劃分區(qū)間。

設(shè)數(shù)組為a［i］，f［i］［j］表示區(qū)間［i，j］的最大值。

則長(zhǎng)度為1的區(qū)間總共有n個(gè)，f［i］［i］=a［i］。

長(zhǎng)度為2的區(qū)間總共有n-1個(gè)。

因?yàn)橹耙呀?jīng)求出了長(zhǎng)度為1的區(qū)間的最大值，所以區(qū)間長(zhǎng)度為2的最大值可以通過(guò)區(qū)間長(zhǎng)度為1的結(jié)果直接推出來(lái)。

接下來(lái)就考慮長(zhǎng)度為3的區(qū)間了嗎？

其實(shí)并不是，因?yàn)榍懊嬉呀?jīng)有了長(zhǎng)度為1和2的，所以可以組合出長(zhǎng)度為3和4的。

那就直接考慮長(zhǎng)度為5的嗎？

如果考慮為5的，那你怎么計(jì)算呢，前面的也推不出長(zhǎng)度為5的結(jié)果啊，至少得有3個(gè)區(qū)間才能推出來(lái)

。

所以接下來(lái)考慮長(zhǎng)度為4的區(qū)間才是正解，總共有n-3個(gè)。

再接下來(lái)自然就是考慮長(zhǎng)度為8的區(qū)間了，總共有n-7個(gè)。

但這里有個(gè)很明顯的問(wèn)題，就是我們的數(shù)組f［i，j］定義的不合理，因?yàn)槔锩婧芏嗟男^(qū)間沒(méi)有用上，比如長(zhǎng)度為3，5，6，7等，所以需要重新定義。 04 狀態(tài)壓縮可以將第二維用于表示區(qū)間長(zhǎng)度，第一維表示區(qū)間起點(diǎn)，對(duì)第二維就可以進(jìn)行狀態(tài)壓縮。

設(shè)f［i，j］表示從i開(kāi)始，長(zhǎng)度為2^j的區(qū)間的最大值，即區(qū)間［i，i+2^j-1］。

則長(zhǎng)度為2^j的區(qū)間就可以通過(guò)左右2個(gè)長(zhǎng)度為2^（j-1）的區(qū)間推出結(jié)果。時(shí)間和空間的復(fù)雜度都為O（nlogn）。

05 區(qū)間分解

那查詢結(jié)果的時(shí)候要怎么處理呢，我們只計(jì)算了長(zhǎng)度為2^j的區(qū)間，并沒(méi)有計(jì)算長(zhǎng)度為3、5、7等區(qū)間的結(jié)果。

所以這個(gè)處理和線段樹(shù)的思想也類似，需要進(jìn)行區(qū)間分解。不過(guò)線段樹(shù)可能分解成很多個(gè)區(qū)間，而稀疏表只需要分解成2個(gè)區(qū)間就可以了。

對(duì)于任意區(qū)間［a，b］，長(zhǎng)度為b-a+1，總可以找到2個(gè)長(zhǎng)度為2^j的區(qū)間，這2個(gè)區(qū)間組合起來(lái)可以完全覆蓋［a，b］，其中j的值為log（b-a+1）。

左邊的區(qū)間左端點(diǎn)從a開(kāi)始，長(zhǎng)度為2^j，即區(qū)間［a，a+2^j-1］。右邊的區(qū)間右端點(diǎn)從b開(kāi)始，長(zhǎng)度為2^j，即區(qū)間［b-2^j+1，b］。

則區(qū)間［a，b］的最大值就是這兩個(gè)區(qū)間中更大的那個(gè)，即max（f［a，j］，f［b-2^j+1，j］）。

06 代碼實(shí)現(xiàn)

代碼實(shí)現(xiàn)了最大值和最小值的獲取。

6.1變量定義

int high［50000］［17］， low［50000］［17］， n， q;

6.1預(yù)處理

void solve（） {

// 枚舉區(qū)間長(zhǎng)度，2^j《=n

for （int j = 1; （1 《《 j） 《= n; ++j） {

// 枚舉左端點(diǎn)i，右端點(diǎn)i+2^j-1《=n-1

for （int i = 0; i + （1 《《 j） 《= n; ++i） {

high［i］［j］ = max（high［i］［j - 1］， high［i + （1 《《 （j - 1））］［j - 1］）;

low［i］［j］ = min（low［i］［j - 1］， low［i + （1 《《 （j - 1））］［j - 1］）;

}

} }

6.1main函數(shù)

int main（） {

cin 》》 n 》》 q;

for （int i = 0; i 《 n; ++i） {

cin 》》 high［i］［0］;

low［i］［0］ = high［i］［0］;

}

solve（）;

for （int i = 0; i 《 q; ++i） {

int a， b;

cin 》》 a 》》 b;

a--;

b--;

int j = （int） （log（b - a + 1.0） / log（2.0））;

int minHeight = min（low［a］［j］， low［b - （1 《《 j） + 1］［j］）;

int maxHeight = max（high［a］［j］， high［b - （1 《《 j） + 1］［j］）;

cout 《《 maxHeight - minHeight 《《 endl;

}

return 0; }

07 總結(jié)

對(duì)于數(shù)據(jù)不變的情況，可以用稀疏表預(yù)處理，這種屬于離線算法。如果要?jiǎng)討B(tài)維護(hù)變化，動(dòng)態(tài)查詢，那就得用在線算法，比如線段樹(shù)。但稀疏表的效率確實(shí)高，有狀態(tài)壓縮和動(dòng)態(tài)規(guī)劃的思想，值得深入研究學(xué)習(xí)。

--- EOF ---

審核編輯 ：李倩