二項演算が非可換な場合のセグメント木のクエリ処理

気になったのでメモ。

モノイド

セグメント木は、完全二分木の各ノードがその子孫の範囲の情報を管理しているようなデータ構造。

図は、配列(緑)に対して対応するセグメント木(青)を表す。
青の2番は、緑の0番から3番までの範囲に演算した結果を保持する。

セグメント木は、和やmax/minなんかの演算結果を持たせるだけでなく、一般にモノイドであればよいらしい。

モノイドは、集合Sと二項演算*:S×S→Sに対して、

• 結合律：(a*b)*c = a*(b*c)
• 単位元の存在：Sの元eが存在して、Sの任意の元aに対して、a*e = e*a = a

を満たすようなものをいう。

二項演算が可換の場合の範囲クエリ処理

ある範囲[l,r)に対して二項演算を行った結果を得たい。

二項演算がsumやmax/minの場合は、蟻本にあるように

• 完全に範囲外
• 完全に範囲内
• 部分的に範囲内

で場合分けして、「部分的に範囲内」の場合再帰するような関数で求められる。

二項演算が非可換の場合の範囲クエリ処理

sumやmax/minは可換なので、上のように実装できているが、非可換な二項演算の場合はどうなるかよくわからなかったので、調べたところ、
http://codeforces.com/blog/entry/18051
このエントリで紹介されていた。(「Non-commutative combiner functions」のところ)

基本的に、演算の左右を明示的に区別して処理すればよいっぽい。(combine(lhs, rhs)関数を用意して処理)

ちなみに上記のエントリだと、query(l,r)関数はlとrに対応する葉ノードから親方向に向かって処理していた。

赤のノードが演算対象。
範囲内の一番端から該当するノードをうまく選んでめぐって演算を繰り返す(l < rの間)。