---
tags: 基礎資料結構
title: ST表 (Sparse Table)
---

# ST表
:::info
### 前言：
它可以解決不帶修改的RMQ (Range Maximum Query)
:::
:::success
### 方法（以RMQ為例）：
- 如果rmq的預處理是對於每個區間都建表，那麼顯然
- 每次查詢的複雜度為 $O(1)$
- 建表的複雜度 $O(n^2)$
- 這個複雜度似乎好大，我們想要把 $n^2$ 變小
- 我們試圖把每個區間拆成若干個區間，並發現每個區間都能拆成兩個可重疊且長度為$2^k(k\in N)$
- 所以我們決定對於每個長度為$2^k(k\in N)$的區間建個表，就是ST表
- 每次查詢的複雜度為 $O(1)$
- 建表的複雜度 $O(n×logn)$
:::
:::info
### 題目
- [模板題 ZJ d539](https://zerojudge.tw/ShowProblem?problemid=d539)
- [變形題 UVa 11235](https://onlinejudge.org/external/112/11235.pdf)
:::