SparseTable(区間最小)

keyword:

カートに追加

overview

構築済みの配列に対して,次のクエリを処理できる. - 区間の最小値を計算する. 0-indexedで,[begin,end).beginを含み,endを含まない. 何度も加減算を繰り返すと内部でオーバーフローを起こす可能性. インデックスは size_t ではなく int で扱う.[TODO] O(log^2N).最大値のみの機能なら出来そう.[TODO]

usage

SparseTable(int n)
; [0,n) の配列を確保する.
T& SparseTable::operator[](size_t i)
; i の要素の参照を得る.build後に更新してはならない.
void SparseTable::build()
; クエリに応えられるように準備する.
void SparseTable::getminrangeIdx(int begin, int end)
; 区間[begin,end)の最小値を計算する

verified

http://yukicoder.me/submissions/172470

references

http://tookunn.hatenablog.com/entry/2016/07/13/211148

code