\( \newcommand{\ord}[1]{\mathcal{O}\left(#1\right)} \newcommand{\abs}[1]{\lvert #1 \rvert} \newcommand{\floor}[1]{\lfloor #1 \rfloor} \newcommand{\ceil}[1]{\lceil #1 \rceil} \newcommand{\opord}{\operatorname{\mathcal{O}}} \newcommand{\argmax}{\operatorname{arg\,max}} \newcommand{\str}[1]{\texttt{"#1"}} \)

2015年7月28日 星期二

[ sparse table ] RMQ問題的稀疏表算法

RMQ問題(Range Minimum/Maximum Query,區間最值問題),通常是給定一條串列s,有若干次的詢問查詢區間L至區間R的最大(小)值。
相信關於RMQ問題使用線段樹的做法很多人都有一定的了解,這邊提供另外一種在線不可修改的做法,稱為稀疏表算法,其預處理時間為\(\ord{NlogN}\),N為串列長度,
查詢時間為\(\ord 1\),是一種高效的演算法。

關於此算法的說明請看http://noalgo.info/489.html
由連結提供的程式碼效能是十分差的,因此這邊提供我的模板(以區間最小值為例):

沒有留言:

張貼留言