ST表

前言：

它可以解決不帶修改的RMQ (Range Maximum Query)

方法（以RMQ為例）：

• 如果rmq的預處理是對於每個區間都建表，那麼顯然
  • 每次查詢的複雜度為
    $O(1)$
  • 建表的複雜度
    $O(n^2)$
• 這個複雜度似乎好大，我們想要把
  $n^2$ 變小
• 我們試圖把每個區間拆成若干個區間，並發現每個區間都能拆成兩個可重疊且長度為
  $2^k(k\in N)$
• 所以我們決定對於每個長度為
  $2^k(k\in N)$的區間建個表，就是ST表
  • 每次查詢的複雜度為
    $O(1)$
  • 建表的複雜度
    $O(n\times logn)$

題目

• 模板題 ZJ d539
• 變形題 UVa 11235