# 稀疏表
###### tags: `Competitive Programming Note` `108 師大附中校隊培訓`

本文已停止更新，新版請至 [WiwiHo 的競程筆記](https://cp.wiwiho.me/)

[108 師大附中校隊培訓簡報](/@wiwiho/S1F04FUcr)

前綴和在經過 $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](https://zerojudge.tw/ShowProblem?problemid=d539) - 區間詢問最大值
- [TIOJ 1338](https://tioj.ck.tp.edu.tw/problems/1338) - 詢問區間內有沒有一個數字整除區間內全部的數字