テストステ論

高テス協会会長が, テストステロンに関する情報をお届けします.

セグメントツリー

蟻本中級編で, プロコン必須のデータ構造として紹介されているセグメントツリーについて, 理解した内容をまとめておく.

セグメントツリーは, 範囲を入力としたクエリを行うためのデータ構造である. 例えば, 配列中[i,j)の中もっとも小さな数値を求めなさいという問題(RMQ)に使うことが出来る.

その本質は, 二分木での管理である. 例えば, 上記[i,j]が[1,8)だったとすると, [1,2)[2,4)[4,8)の3つの2i長クエリに分解して, それぞれをlog nで実行してかき集めて, 集約する. 各サブクエリは独立なので, 並列実行も可能だろうと思う. 当然, map-reduceのようなものとも相性が良いだろう.

セグメントツリーの各ノード(セグメントツリーはブランチとリーフの区別をしない)には, いかなるデータも載せることが可能だろう. 仮にその型をTとする. その上で, 2つの子ノードから親ノードを計算する計算方法(opとする)が必要となる. 仮にデータがない場合の値T0も必要だろう. たぶん, T0とT型の任意の値Tiについては, T0 op Ti=Ti op T0=T0となることが必要である(つまりT0は単位元).

これら(型T, 単位元T0, 二項演算子op)が与えられたらセグメントツリーを作ることが出来る. 例えば, RMQの例でいうと, T=int, T0=INF, op=minとすれば良い. つまり, セグメントツリーを実装する場合は, class SegmentTree<T, T0, op>となり, updateとqueryを実装することになる.

セグメントツリーの応用例としては, 以下のようなものが蟻本には書かれている.

  • 区間和を持つ. T=int, T0=0, op=+
  • ソートされた数列を持つ. T=[int], T0=[], op=sort . (++)
  • 区間に対してある値xを足すクエリがある場合. (あらかじめ区間を分割する必要があるので, 区間を分割する方法は公開しなければならないだろう. あるいは, updateを範囲に対して行うように一般化すべきか.