Acted Monoid: Range Add Range Sum
(algebra/range_add_range_sum.hpp)

• View this file on GitHub
• Last update: 2026-10-23 22:06:19+09:00
• Include: #include "algebra/range_add_range_sum.hpp"

概要

• 区間加算・区間和。lazy_segtree<range_add_range_sum<T>> のように使う。

使い方

• S = {T sum; int len}, F = T
• from(v): 値 v 1 個分の要素 {v, 1} を返す。初期化や一点更新ではこれで S を作る。
• prod(l, r).sum が区間和。

Verified with

• test/aoj/DSL_2_G.test.cpp
• test/unit/monoid.test.cpp

Code

#pragma once
template <class T>
struct range_add_range_sum {
    struct S {
        T sum;
        int len;
    };
    using F = T;
    static S op(S a, S b) {
        return {a.sum + b.sum, a.len + b.len};
    }
    static S e() {
        return {T(0), 0};
    }
    static S mapping(F f, S x) {
        return {x.sum + f * x.len, x.len};
    }
    static F composition(F f, F g) {
        return f + g;
    }
    static F id() {
        return T(0);
    }
    static constexpr bool composition_commutative = true;
    static S from(T v) {
        return {v, 1};
    }
};

#line 2 "algebra/range_add_range_sum.hpp"
template <class T>
struct range_add_range_sum {
    struct S {
        T sum;
        int len;
    };
    using F = T;
    static S op(S a, S b) {
        return {a.sum + b.sum, a.len + b.len};
    }
    static S e() {
        return {T(0), 0};
    }
    static S mapping(F f, S x) {
        return {x.sum + f * x.len, x.len};
    }
    static F composition(F f, F g) {
        return f + g;
    }
    static F id() {
        return T(0);
    }
    static constexpr bool composition_commutative = true;
    static S from(T v) {
        return {v, 1};
    }
};

Back to top page