Sparse Table

有一個序列 ，有 筆詢問，每筆詢問求 的區間最大值。

如果是要求區間和的話，前綴和在經過 預處理後，可以 求得區間和，但顯然這樣的方式不能用在區間最大或最小值上。那麼有沒有辦法可以在經過預處理後 得到區間極值呢？

如果算出每一個 長的區間中的極值，在詢問的時候，就可以把一些區間拼起來，得到我們想要的答案。而且計算也很方便，因為每個 長的區間，都是兩個 長的區間拼起來。

（ 切塊示意圖，事實上會計算到的區間不只這樣。）

令 為以元素 為起點，長 的區間中的極值，也就是說，這個區間的範圍是 （會超出範圍的就不用算，也用不到）。

長度 的區間可以分割成兩個長度 的區間，起點分別是 和 。因此， 的值是 和 取極值。

當 時，，因此以 為起點， 大小的區間長度只有 ，內容也只有第 個元素，因此， 就是第 個元素。

最後，當我們要求 的極值，就用兩個長 的區間來湊出答案就好，其中一個的起點是 ，另一個起點是 ，因此，令 ，我們可以用 和 來得到我們想要的答案，它們有部分重疊也沒有關係，只要兩個區間範圍聯集起來是我們想要的區間就好，極值一定會出現在其中一區間。

這樣一來，我們就可以先預處理整個 了。我們需要求出以每個元素為起點，各個 長的區間的極值，至於 的最大值應該要是多少？會用到的最大的 會出現在詢問區間是整個數列的時候，我們會需要 ，所以 的範圍只需要 ，預處理複雜度是 。

因為同一個元素會被很多區間包含，所以 Sparse Table 不能做修改。

練習題

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