モノイド
セグメント木にはモノイドが乗りますが、これは十分条件です。 セグメント木には半群も乗ります。
セグメント木に半群を乗せる場合、未初期化のノードはNoneで表現することになります。
すなわち、ノードにはOption<S>が格納されます。
Option<S>上の二項演算を以下で定義すると、半群をモノイドに拡張できます。
#![allow(unused)] fn main() { fn binary_operation<S>(lhs: Option<S>, rhs: Option<S>) -> Option<S> { match (lhs, rhs) { (Some(lhs), Some(rhs)) => todo!("lhs ⋅ rhs"), (Some(lhs), None) => Some(lhs), (None, Some(rhs)) => Some(rhs), (None, None) => None } } }
このようにモノイドと半群の区別はあまり重要ではありません。
実装上単位元があると便利なので、seg_libではモノイドを採用しました。
#![allow(unused)] fn main() { pub trait Monoid { /// The set of the monoid. type Set; /// If [`Self::combine`] is commutative, some operations can be optimized. /// /// If unsure about the commutativity, use [`false`] for safety. /// /// # Commutative low /// /// ```text /// a · b = b · a ∀ a, b ∈ Set /// ``` const IS_COMMUTATIVE: bool; /// Returns the identity element. fn identity() -> Self::Set; /// Combines the two elements and returns the result. /// /// # Warning /// /// If the operation is **not** commutative, the position of the arguments matters. fn combine(lhs_or_prev: &Self::Set, rhs_or_new: &Self::Set) -> Self::Set; } }
Setをジェネリック型ではなく関連型としてもっています。
こうすることで、ジェネリックパラメーターが1つ減り、実装がシンプルになります。
#![allow(unused)] fn main() { pub struct SegmentTree<Query> where Query: Monoid, { /// Use `Box<T>` because the length is significant as follows. /// /// - data\[0\] : dummy node (meaningless) /// - data\[1..n\] : nodes to store the combined value of the children. /// - data\[n..2n\]: nodes to store value for each cell. data: Box<[<Query as Monoid>::Set]>, /// `len` (number of elements) and offset (dummy + cache) len_or_offset: usize, // /// This and its ancestors are all invalid (cached result may be broken) // min_invalid_node: usize, } }
おまけ
セグメント木には半群ですらない代数的構造も乗ります。 問題にしている範囲で半群のように振舞えば何でもよいのです。