Library/DataStructure/Accumulation.hpp

• View this file on GitHub
• Last update: 2024-12-27 16:29:20+09:00
• Include: #include "Library/DataStructure/Accumulation.hpp"

Depends on

• Library/Algebraic/Group.hpp

Required by

• Library/DataStructure/Accumulation2D.hpp

Verified with

• Test/DataStructure/Accumulation2D_sum.test.cpp
• Test/DataStructure/Accumulation_sum.test.cpp
• Test/DataStructure/Accumulation_xor.test.cpp

Code

#pragma once

#include <algorithm>

#include <vector>


#include "../Algebraic/Group.hpp"


namespace mtd {

  namespace type {

    using inv = decltype([](auto x) { return -x; });
    using op = decltype([](auto x, auto y) { return x + y; });
    template <class P>
    using AdditiveGroup = Group<P, P(0), op, inv>;

  }  // namespace type


  template <group Group = type::AdditiveGroup<long long>>
  class Accumulation {
    using S = decltype(Group().m_val);

    const int size;
    std::vector<Group> sumList;

  public:
    constexpr Accumulation() = delete;
    constexpr Accumulation(const std::vector<Group>& v)
        : size(v.size()), sumList(size + 1) {
      for (int i = 0; i < size; ++i) {
        sumList[i + 1] = sumList[i].binaryOperation(v[i]);
      }
    }
    constexpr Accumulation(const std::vector<S>& v)
        : Accumulation(std::vector<Group>(v.begin(), v.end())) {}

    constexpr auto get(int n) const { return sumList[n + 1].m_val; }
    constexpr auto get(int l, int r) const {
      if (r < l) { return Group::_element; }
      l = std::max(l, 0);
      r = std::min(r, size - 1);
      return sumList[r + 1].binaryOperation(sumList[l].inverse()).m_val;
    }

    constexpr friend std::ostream& operator<<(std::ostream& os,
                                              const Accumulation<Group>& acc) {
      for (const auto& x : acc.sumList) { os << x << " "; }
      return os;
    }
  };

}  // namespace mtd

#line 2 "Library/DataStructure/Accumulation.hpp"

#include <algorithm>

#include <vector>


#line 2 "Library/Algebraic/Group.hpp"

#include <iostream>

namespace mtd {

  template <class S,    // set
            S element,  // identity element
            class op,   // binary operation
            class inv   // inverse operation
            >
  requires std::is_invocable_r_v<S, op, S, S>
  struct Group {
    using value_type = S;
    constexpr static S _element = element;
    using op_type = op;
    using inv_type = inv;

    S m_val;
    constexpr Group() : m_val(element) {}
    constexpr Group(S val) : m_val(val) {}
    constexpr Group inverse() const { return inv()(m_val); }
    constexpr Group binaryOperation(const Group& g) const {
      return op()(m_val, g.m_val);
    }
    constexpr friend std::ostream& operator<<(
        std::ostream& os, const Group<S, element, op, inv>& g) {
      return os << g.m_val;
    }
  };

  namespace __detail {
    template <typename T,
              template <typename, auto, typename, typename> typename S>
    concept is_group_specialization_of = requires {
      typename std::enable_if_t<
          std::is_same_v<T, S<typename T::value_type, T::_element,
                              typename T::op_type, typename T::inv_type>>>;
    };
  }  // namespace __detail

  template <typename G>
  concept group = __detail::is_group_specialization_of<G, Group>;

}  // namespace mtd
#line 7 "Library/DataStructure/Accumulation.hpp"

namespace mtd {

  namespace type {

    using inv = decltype([](auto x) { return -x; });
    using op = decltype([](auto x, auto y) { return x + y; });
    template <class P>
    using AdditiveGroup = Group<P, P(0), op, inv>;

  }  // namespace type


  template <group Group = type::AdditiveGroup<long long>>
  class Accumulation {
    using S = decltype(Group().m_val);

    const int size;
    std::vector<Group> sumList;

  public:
    constexpr Accumulation() = delete;
    constexpr Accumulation(const std::vector<Group>& v)
        : size(v.size()), sumList(size + 1) {
      for (int i = 0; i < size; ++i) {
        sumList[i + 1] = sumList[i].binaryOperation(v[i]);
      }
    }
    constexpr Accumulation(const std::vector<S>& v)
        : Accumulation(std::vector<Group>(v.begin(), v.end())) {}

    constexpr auto get(int n) const { return sumList[n + 1].m_val; }
    constexpr auto get(int l, int r) const {
      if (r < l) { return Group::_element; }
      l = std::max(l, 0);
      r = std::min(r, size - 1);
      return sumList[r + 1].binaryOperation(sumList[l].inverse()).m_val;
    }

    constexpr friend std::ostream& operator<<(std::ostream& os,
                                              const Accumulation<Group>& acc) {
      for (const auto& x : acc.sumList) { os << x << " "; }
      return os;
    }
  };

}  // namespace mtd

Back to top page