モノイド作用

遅延伝搬セグメント木ではいくつかの要素をまとめて更新します。取得クエリに対応するモノイドを $(Q, \cdot_{Q}, e_{Q})$ 、更新クエリに対応するモノイドを $(U, \cdot_{U}, e_{U})$ とかきます。モノイド作用は2つのモノイドをつなぐ糊のようなものです。遅延伝搬セグメント木が正しく動作するためには「いくつかの要素をまとめて更新する」ことで「各要素をそれぞれ更新した結果」を再現できなければなりません。

定義（モノイド作用）

区間クエリに対応するモノイドを $(Q, \cdot_{Q}, e_{Q})$ 、更新クエリに対応するモノイドを $(U, \cdot_{U}, e_{U})$ とする。 $* : U \times Q ⟶ Q$ が下記を満たすとき、これをモノイド作用という。

（結合法則） $\forall u_{1}, u_{2} \in U, \forall q \in Q, (u_{1} \cdot_{U} u_{2}) * q = u_{1} * (u_{2} * q)$
（分配法則） $\forall u \in U, \forall q_{1}, q_{2} \in Q, (u * q_{1}) \cdot_{Q} (u * q_{2}) = u * (q_{1} \cdot_{Q} q_{2})$

実装例（モノイド作用）

#![allow(unused)]
fn main() {
pub trait MonoidAction {
    /// The set of the monoid for update operation.
    type Map: Monoid;
    /// The set of the monoid for query operation.
    type Set: Monoid;

    /// Set [`true`] to use the segment size in [`Self::act()`]
    const USE_SEGMENT_SIZE: bool;

    /// Acts the mapping on the element and returns the result.
    ///
    /// # Size dependency
    ///
    /// You can access segment size if you want.
    /// This is equivalent to attaching the segment size information to [`Self::Set`] but more performant.
    fn act(
        mapping: &<Self::Map as Monoid>::Set,
        element: &<Self::Set as Monoid>::Set,
        size: Option<usize>,
    ) -> <Self::Set as Monoid>::Set;
}
}

Mapは更新クエリ、Setは取得クエリに対応します。

#![allow(unused)]
fn main() {
pub struct LazySegmentTree<Action>
where
    Action: MonoidAction,
{
    data: Box<[<<Action as MonoidAction>::Set as Monoid>::Set]>,
    lazy: Box<[<<Action as MonoidAction>::Map as Monoid>::Set]>,

    /// calculate if [`MonoidAction::USE_SEGMENT_SIZE`] is `true`.
    segment_size: Option<Box<[usize]>>,
}
}

区間幅の利用

モノイド作用に区間幅の情報を利用したいことがあります。これは取得クエリに区間幅の情報を付加する（ $Q \to Q \times N$ ）ことで実現できますが、不変量を何度も計算し直すことになり非効率です。初期化時に $Θ (N)$ で計算し、計算済みの値を取得すると良いです。

Keyboard shortcuts

Segment Tree Library Book

モノイド作用

区間幅の利用