稀疏表

tags: Competitive Programming Note 108 師大附中校隊培訓

本文已停止更新，新版請至 WiwiHo 的競程筆記

108 師大附中校隊培訓簡報

前綴和在經過

$O(n)$ 預處理後，可以

$O(1)$ 求得區間和，但顯然這樣的方式不能用在區間最大或最小值上。那麼有沒有辦法可以在經過預處理後

$O(1)$ 得到區間最大或最小值呢？

一樣用切塊的方法來想，但是我們要把塊「合併」，兩個元素可以合成一個長度為

$2$ 的塊，兩個長度為

$2$ 的塊可以合成長度為

$4$ 的塊……兩個長度為

$2^{i-1}$ 的塊可以合成長度為

$2^i$ 的塊，而且有很多塊是重疊的。

用一個 DP 的方式來做：

令

$s[i][j]$ 為以元素

$i$ 為起點，長

$2^j$ 的塊中的最大值或最小值，也就是說，這個塊的範圍是

$[i,i+2^j-1]$（會超出範圍的就不用算，也用不到）。

長度

$2^j$ 的塊可以分割成兩個長度

$2^{j-1}$ 的塊，起點分別是

$i$ 和

$i+2^{j-1}$。因此，

$s[i][j]$ 的值是

$s[i][j-1]$ 和

$s[i+2^{j-1}][j-1]$ 取最大或最小。

當

$j=0$ 時，

$2^j=1$，因此以

$i$ 為起點，

$2^j$ 大小的塊長度只有

$1$，內容也只有第

$i$ 個元素，因此，

$s[i][0]$ 就是第

$i$ 個元素。

最後，當我們要求

$[l,r]$ 的最大或最小值，就用兩個長

$2^{\lfloor {\log }_2(r-l+1)\rfloor }$ 的塊來湊出答案就好，其中一個的起點是

$l$，另一個起點是

$r-2^{\lfloor {\log }_2(r-l+1)\rfloor }+1$，因此，令

$k=\lfloor {\log }_2(r-l+1)\rfloor$，我們可以用

$s[l][k]$ 和

$s[r-2^k+1][k]$ 來得到我們想要的答案，它們有部分重疊也沒有關係，只要兩塊範圍聯集起來是我們想要的區間就好，最大或最小值一定會出現在其中一塊。

這樣一來，我們就可以先預處理整個

$s$ 了。我們需要求出以每個元素為起點，各個

$2^j$ 長的塊的最大或最小值，至於

$j$ 的最大值應該要是多少？會用到的最大的

$j$ 會出現在詢問區間是整個數列的時候，我們會需要

$j=\lfloor {\log }_{2}n\rfloor$，所以

$j$ 的範圍只需要

$[0,\lfloor {\log }_{2}n\rfloor ]$，預處理複雜度是

$O(n\log n)$。

稀疏表顯然不能做修改，因為一個元素會被好幾個塊包含，數量實在太多了，如果做修改會需要改非常多數字，顯然沒有效率。

練習題

• ZeroJudge d539 - 區間詢問最大值
• TIOJ 1338 - 詢問區間內有沒有一個數字整除區間內全部的數字