phyllo’s algorithm note

レッドコーダーへの道のりは遠い。休んでる場合じゃない!

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

気になったのでメモ。

モノイド

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

f:id:phyllo_algo:20170406004009p:plain
図は、配列(緑)に対して対応するセグメント木(青)を表す。
青の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」のところ)


query(l,r)関数はlとrに対応する葉ノードから親方向に向かって処理している。
f:id:phyllo_algo:20170406004014p:plain
赤のノードが演算対象。
範囲内の一番端から該当するノードをうまく選んでめぐって演算を繰り返す(l < rの間)。