遅延伝搬セグメント木

値のセグメント木と作用のセグメント木を組み合わせて範囲作用・範囲縮約できるようにしたデータ構造

• 値の集合V(モノイド)
  • 二項演算 $f(x,y)\to z$where $x,y,z\in V$ モノイドであること | 二項演算 | 結合則 | 単位元 | | — | — | — | — | | add | a + (b + c) = (a + b) + c | 0 | 0 + x = x + 0 = x | | mul | a * (b * c) = (a * b) * c | 1 | 1 * x = x * 1 = 1 | | max | max(a, max(b, c)) = max(max(a, b), c) | -INF | max(-INF, x) = max(x, -INF) = x |
  • この部分はセグメント木と同じ制約
  • ある範囲に含まれる複数の値に対して二項演算を繰り返して一つの値にすることを「範囲縮約」と呼んでる。
• 作用の集合A (action)
  • 作用: $f(x)\to y$ where $x,y\in V,f\in A$
  • 作用の合成: $c(f,g)\to h$ where $f,g\in A,h(x)=g(f(x))$ : | 作用 | 作用の合成 | 単位元 | | — | — | — | | add | c(add(a), add(b)) = add(a + b) | add(0) | | chmin | c(chmin(a), chmin(b)) = chmin(min(a, b)) | chmin(INF) | | set | c(set(a), set(b)) = set(a if b is None else b) | set(None) |
  • ある範囲に含まれる複数の値に対して作用をすることを「範囲作用」と呼んでる
  • 作用fは文字通り関数オブジェクトとして実装しても動きはするが、遅いので、普通は整数1でadd(1)を表現するなどが行われる
    • この整数を、作用を特定するためのパラメータという意味で「作用パラメータ」と呼ぶことにする
    • 実装上は「作用の対象となる値」と「作用パラメータ」を引数に取って「作用後の値」を返す関数が必要になる
    • この関数を、遅延された作用の評価を強制する関数ということで作用強制関数action_forceと呼んでる
    • 世の中の説明の多くで「作用」「作用パラメータ」「作用強制関数」の3つを異なる名前で呼び分けないで、まとめて「作用」と呼んでて、僕はしばらく混乱した。
• 値の二項演算、値の単位元、作用の合成演算、作用強制関数、作用の単位元、の5つが必要
• 範囲縮約が必要ない、点取得でいい場合
  • 二項演算で下から上に伝搬していくプロセスが不要になる
    • =値のセグメント木が不要
  • →半分遅延セグメント木
• 点取得で、かつ作用の合成が可換の場合
  • 可換: $c(f,g)=c(g,f)$
    • 例: c(add(a), add(b)) = c(add(b), add(a)) = add(a + b)
    • addやchminでは成り立つ、setでは成り立たない
  • この時、作用を追加する際に前の作用を下に伝搬する必要がなくなる
    • →双対セグメント木

ノードのサイズに関して

• 例えば「1増やす」という作用を葉が4つあるようなノードに強制する場合、値は4増える
• これをコードで実現しようとすると、作用強制関数はノードのサイズを引数に受け取る必要がある
• 数学的構造から逸脱してて疑問に思った
• これは数学的には
  • 値の集合がintではなく(int, size)
  • 葉の値は(int, 1)
• 実際にこの通りにタプルで値を持って、二項演算でサイズを計算しても良い
• サイズはノードのIDから計算できるので値を持たないことで高速化ができる
• 問題によっては値の二項演算にもサイズが必要になる
  • ACL Beginner Contest

表記揺れ

• 遅延セグメント木
• 遅延伝播segment木