crates/algebra/src/lib.rs

• View this file on GitHub
• Last update: 2025-08-03 12:43:51+09:00

Required by

• crates/data_structure/dual_segtree/src/lib.rs
• crates/data_structure/dynamic_segtree/src/lib.rs
• crates/data_structure/lazy_segtree/src/lib.rs
• crates/data_structure/lazy_segtree_utils/src/lib.rs
• crates/data_structure/potentialized_unionfind/src/lib.rs
• crates/data_structure/segtree/src/lib.rs
• crates/data_structure/segtree_2d_compressed/src/lib.rs
• crates/data_structure/segtree_2d_dense/src/lib.rs
• crates/data_structure/sparse_table/src/lib.rs
• crates/data_structure/sparse_table_on_segtree/src/lib.rs
• crates/math/matrix/src/lib.rs
• crates/tree/euler_tour/src/lib.rs
• crates/tree/rerooting/src/lib.rs
• crates/utils/monoid_utils/src/lib.rs
• crates/wavelet/wavelet_matrix_fenwick/src/lib.rs
• crates/wavelet/wavelet_matrix_segtree/src/lib.rs
• verify/AtCoder/abc222f/src/main.rs
• verify/AtCoder/abc312g/src/main.rs
• verify/AtCoder/abc328f/src/main.rs
• verify/AtCoder/abc348e/src/main.rs
• verify/AtCoder/alpc_l_lazy_seg/src/main.rs
• verify/AtCoder/typical_068/src/main.rs

Verified with

• verify/AOJ/dsl_2d_dual_seg/src/main.rs
• verify/AOJ/dsl_2d_dual_seg_non_commutative/src/main.rs
• verify/AOJ/dsl_2f_lazy_seg/src/main.rs
• verify/AOJ/dsl_2h_lazy_seg_commutative/src/main.rs
• verify/AOJ/no_1068/src/main.rs
• verify/AOJ/no_2842/src/main.rs
• verify/yosupo/point_add_rect_sum_wavelet_seg/src/main.rs
• verify/yosupo/point_add_rectangle_sum_seg2d/src/main.rs
• verify/yosupo/point_set_range_composite/src/main.rs
• verify/yosupo/point_set_range_composite_large_array/src/main.rs
• verify/yosupo/range_affine_range_sum_lazy_seg/src/main.rs
• verify/yosupo/rectangle_add_point_get/src/main.rs
• verify/yosupo/staticrmq_sparse_table/src/main.rs
• verify/yosupo/unionfind_with_potential_non_commutative_group/src/main.rs
• verify/yosupo/vertex_set_path_composite/src/main.rs
• verify/yukicoder/no_1625/src/main.rs
• verify/yukicoder/no_1625_wavelet/src/main.rs
• verify/yukicoder/no_789_dynamic/src/main.rs

Code

//! `Algrebra`では、データ構造に乗せる代数構造のtraitを提供します。
use std::fmt::Debug;

/// 可換  
pub trait Commutative {}

/// 作用  
/// 作用自体もモノイドであることを要求  
/// 作用素を合成させてから作用させるのと、作用素を一つ一つ作用させる結果が同じであることを要求
pub trait Action: Debug + Clone {
    /// 作用の対象
    type Target: Clone;
    /// 恒等写像
    fn id_action() -> Self;
    /// 作用の合成(selfが先、rhsが後)  
    /// (atcoder libraryとは作用の順が逆なので注意)
    fn composition(&mut self, rhs: &Self);
    /// 作用の適用
    fn apply(&self, target: &mut Self::Target);
}

/// モノイド
pub trait Monoid: Debug {
    /// モノイドの要素
    type Target: Debug + Clone;
    /// 単位元
    fn id_element() -> Self::Target;
    /// 二項演算
    fn binary_operation(a: &Self::Target, b: &Self::Target) -> Self::Target;
}

/// 自己準同型性を要求  
/// つまり区間和への適用と、各要素への適用の区間和が一致することを要求  
pub trait ActionMonoid {
    /// 作用の対象のモノイド
    type M: Monoid;
    /// 作用素のモノイド
    type A: Action<Target = <Self::M as Monoid>::Target>;
}

/// 冪等なモノイド  
/// つまり x = x op x が成り立つようなモノイド  
/// SparseTableに乗る
pub trait IdempotentMonoid: Monoid {}

/// 群   
/// モノイドに加えて、逆元を持つ  
pub trait Group: Monoid {
    fn inverse(a: &Self::Target) -> Self::Target;
}

/// 半環  
/// 加算は可換モノイド  
/// 乗算はモノイド  
/// 乗算は加法に対して分配法則を満たす a*(b+c) = a*b + a*c, (a+b)*c = a*c + b*c  
/// 加算の単位元は乗算の零元 0*a=a*0=0
pub trait Semiring: Debug + Clone + Eq {
    type Target: Debug + Clone + Eq;
    fn zero() -> Self::Target;
    fn one() -> Self::Target;
    fn add_assign(a: &mut Self::Target, b: &Self::Target);
    fn mul(a: &Self::Target, b: &Self::Target) -> Self::Target;
}

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.13.9/x64/lib/python3.13/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ~~~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.13.9/x64/lib/python3.13/site-packages/onlinejudge_verify/languages/rust.py", line 288, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page