This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub suisen-cp/cp-library-cpp
#include "library/util/cumulative_sum.hpp"
#ifndef SUISEN_CUMULATIVE_SUM #define SUISEN_CUMULATIVE_SUM #include <cassert> #include <vector> #include "library/util/default_operator.hpp" namespace suisen { template <typename T, auto zero = default_operator::zero<T>, auto add = default_operator::add<T>, auto sub = default_operator::sub<T>> struct CumulativeSum { CumulativeSum() = default; CumulativeSum(const std::vector<T> &a) : n(a.size()), s(n + 1, zero()) { for (size_t i = 0; i < n; ++i) s[i + 1] = add(a[i], s[i]); } T operator()(size_t l, size_t r) const { assert(l <= r and r <= n); return sub(s[r], s[l]); } T sum(size_t l, size_t r) const { return (*this)(l, r); } void push_back(const T& v) { if (s.empty()) s.push_back(zero()); T new_sum = add(s.back(), v); ++n, s.push_back(std::move(new_sum)); } private: size_t n; std::vector<T> s; }; } #endif // SUISEN_CUMULATIVE_SUM
#line 1 "library/util/cumulative_sum.hpp" #include <cassert> #include <vector> #line 1 "library/util/default_operator.hpp" namespace suisen { namespace default_operator { template <typename T> auto zero() -> decltype(T { 0 }) { return T { 0 }; } template <typename T> auto one() -> decltype(T { 1 }) { return T { 1 }; } template <typename T> auto add(const T &x, const T &y) -> decltype(x + y) { return x + y; } template <typename T> auto sub(const T &x, const T &y) -> decltype(x - y) { return x - y; } template <typename T> auto mul(const T &x, const T &y) -> decltype(x * y) { return x * y; } template <typename T> auto div(const T &x, const T &y) -> decltype(x / y) { return x / y; } template <typename T> auto mod(const T &x, const T &y) -> decltype(x % y) { return x % y; } template <typename T> auto neg(const T &x) -> decltype(-x) { return -x; } template <typename T> auto inv(const T &x) -> decltype(one<T>() / x) { return one<T>() / x; } } // default_operator namespace default_operator_noref { template <typename T> auto zero() -> decltype(T { 0 }) { return T { 0 }; } template <typename T> auto one() -> decltype(T { 1 }) { return T { 1 }; } template <typename T> auto add(T x, T y) -> decltype(x + y) { return x + y; } template <typename T> auto sub(T x, T y) -> decltype(x - y) { return x - y; } template <typename T> auto mul(T x, T y) -> decltype(x * y) { return x * y; } template <typename T> auto div(T x, T y) -> decltype(x / y) { return x / y; } template <typename T> auto mod(T x, T y) -> decltype(x % y) { return x % y; } template <typename T> auto neg(T x) -> decltype(-x) { return -x; } template <typename T> auto inv(T x) -> decltype(one<T>() / x) { return one<T>() / x; } } // default_operator } // namespace suisen #line 7 "library/util/cumulative_sum.hpp" namespace suisen { template <typename T, auto zero = default_operator::zero<T>, auto add = default_operator::add<T>, auto sub = default_operator::sub<T>> struct CumulativeSum { CumulativeSum() = default; CumulativeSum(const std::vector<T> &a) : n(a.size()), s(n + 1, zero()) { for (size_t i = 0; i < n; ++i) s[i + 1] = add(a[i], s[i]); } T operator()(size_t l, size_t r) const { assert(l <= r and r <= n); return sub(s[r], s[l]); } T sum(size_t l, size_t r) const { return (*this)(l, r); } void push_back(const T& v) { if (s.empty()) s.push_back(zero()); T new_sum = add(s.back(), v); ++n, s.push_back(std::move(new_sum)); } private: size_t n; std::vector<T> s; }; }