Segment Tree

説明

完全2分木である。区間に対する様々な操作が $O(logN)$ で実現できるが、一般的なクエリである区間の最小を実装してある。

---

情報

項目	データ
計算量	$O(\log N)$

関数

SegmentTree(n)
機能	葉が $n$ の完全平衡二分木を生成する。初期値は最大は-INF,最小はINF,総和は0。

update(k, x)
機能	$k$ 番目の要素を $x$ にする。

rmq(a, b)
機能	[a, b) の区間の最小を求める。

実装例

問題例

#	ソース	難易度
AOJ 2431 - 引越し	JAG夏合宿2012	★★★