library/datastructure/CumulativeMonoid.hpp

View this file on GitHub
Last update: 2025-11-24 18:49:07+09:00
Include: #include "library/datastructure/CumulativeMonoid.hpp"

Depends on

Code

#include "library/algebra/monoid/Concepts.hpp"

template <monoid M> class CumulativeMonoid {
    using T = typename M::value_type;
    std::vector<T> pre, suf;

  public:
    CumulativeMonoid() : pre(1, M::unit()), suf(pre) {}
    CumulativeMonoid(const std::vector<T> &v)
        : pre(v.size() + 1, M::unit()), suf(pre) {
        for (int i = 0; i < v.size(); i++)
            pre[i + 1] = M::op(pre[i], v[i]);
        for (int i = v.size() - 1; i >= 0; i--)
            suf[i] = M::op(v[i], suf[i + 1]);
        assert(pre.back() == suf[0]);
    }
    //[0,r)
    T pre_sum(int r) { return pre[r]; }
    // [l,n)
    T suf_sum(int l) { return suf[l]; }

    T sum() { return pre.back(); }
};

#line 2 "library/algebra/monoid/Concepts.hpp"

template <class M>
concept monoid = requires(typename M::value_type x) {
    { M::op(x, x) } -> std::same_as<typename M::value_type>;
    { M::Lchop(x, x) };
    { M::Rchop(x, x) };
    { M::unit() } -> std::same_as<typename M::value_type>;
};
#line 2 "library/datastructure/CumulativeMonoid.hpp"

template <monoid M> class CumulativeMonoid {
    using T = typename M::value_type;
    std::vector<T> pre, suf;

  public:
    CumulativeMonoid() : pre(1, M::unit()), suf(pre) {}
    CumulativeMonoid(const std::vector<T> &v)
        : pre(v.size() + 1, M::unit()), suf(pre) {
        for (int i = 0; i < v.size(); i++)
            pre[i + 1] = M::op(pre[i], v[i]);
        for (int i = v.size() - 1; i >= 0; i--)
            suf[i] = M::op(v[i], suf[i + 1]);
        assert(pre.back() == suf[0]);
    }
    //[0,r)
    T pre_sum(int r) { return pre[r]; }
    // [l,n)
    T suf_sum(int l) { return suf[l]; }

    T sum() { return pre.back(); }
};