# 進階資料結構與莫隊算法—稀疏表 ###### tags: `108 師大附中校隊培訓` ###### wiwiho --- 前綴和在經過 $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)$ --- 稀疏表不能做修改 因為一個元素會被好幾個塊包含 數量很多，沒效率