累積和
(library/util/cumulative_sum.hpp)

• View this file on GitHub
• Last update: 2023-07-09 04:04:16+09:00
• Include: #include "library/util/cumulative_sum.hpp"

累積和

Depends on

• Default Operator (library/util/default_operator.hpp)

Code

#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;
    };
}

Back to top page