セグメント木を用いてRMQを実装する
セグメント木とは
セグメント木とはある区間における状態を保持させておくためのデータ構造である。
区間を表すそれぞれのノードに様々な値を保持させておくことで、いろいろな機能を持つ木を作成することができる。
RMQとは
Range Minimum Queryとは、配列に格納されているNこの数値にたいして、範囲を指定することでその区間の最小値を取得するというものだ。 セグメント木を使用することで、以下の操作を実現する。
数列 a0, a1, a2, ..., a(n-1)において
- 範囲[s, t]が与えられた時にインデックス0 <= s, t < nにおける最小値をO(log n)で取得する
- インデックス0 <= i < n と数値xが与えられた時に、aiをxに更新する操作をO(log n)で行う
セグメント木の実装方法
セグメント木は配列によって値を保持させる。インデックスの貼り方は以下の通り。
よって子ノードと親ノードのアクセス方法は以下の通り。
- 親ノードへのアクセス: (n-1) / 2
- 子ノードへのアクセス: 2n + 1, 2n + 2
また、元の配列のインデックスからセグメント木のインデックスへは(n + i - 1)でアクセスできる。
