Library/DataStructure/Accumulation2D.hpp

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

Depends on

• Library/Algebraic/Group.hpp
• Library/DataStructure/Accumulation.hpp

Verified with

• Test/DataStructure/Accumulation2D_sum.test.cpp

Code

#pragma once
#include <vector>


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

#include "./Accumulation.hpp"


namespace mtd {

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

    const int h;
    const int w;
    std::vector<std::vector<Group>> sumList;

  public:
    constexpr Accumulation2D() = delete;
    constexpr Accumulation2D(const std::vector<std::vector<S>>& v)
        : h(v.size()),
          w(v[0].size()),
          sumList(h + 1, std::vector<Group>(w + 1)) {
      for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) { sumList[i + 1][j + 1] = v[i][j]; }
      }
      for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w + 1; ++j) {
          sumList[i + 1][j] = sumList[i + 1][j].binaryOperation(sumList[i][j]);
        }
      }
      for (int i = 0; i < h + 1; ++i) {
        for (int j = 0; j < w; ++j) {
          sumList[i][j + 1] = sumList[i][j + 1].binaryOperation(sumList[i][j]);
        }
      }
    }
    constexpr S get(int y, int x) { return sumList[y + 1][x + 1].m_val; }
    constexpr S get(int y1, int x1, int y2, int x2) {
      if (y2 < y1 || x2 < x1) { return Group().m_val; }
      x1 = std::max(x1, 0);
      y1 = std::max(y1, 0);
      y2 = std::min(y2, h - 1);
      x2 = std::min(x2, w - 1);
      return sumList[y2 + 1][x2 + 1]
          .binaryOperation(sumList[y1][x1])
          .binaryOperation(sumList[y2 + 1][x1].inverse())
          .binaryOperation(sumList[y1][x2 + 1].inverse())
          .m_val;
    }
  };

}  // namespace mtd

#line 2 "Library/DataStructure/Accumulation2D.hpp"
#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 2 "Library/DataStructure/Accumulation.hpp"

#include <algorithm>

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

#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

#line 6 "Library/DataStructure/Accumulation2D.hpp"

namespace mtd {

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

    const int h;
    const int w;
    std::vector<std::vector<Group>> sumList;

  public:
    constexpr Accumulation2D() = delete;
    constexpr Accumulation2D(const std::vector<std::vector<S>>& v)
        : h(v.size()),
          w(v[0].size()),
          sumList(h + 1, std::vector<Group>(w + 1)) {
      for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) { sumList[i + 1][j + 1] = v[i][j]; }
      }
      for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w + 1; ++j) {
          sumList[i + 1][j] = sumList[i + 1][j].binaryOperation(sumList[i][j]);
        }
      }
      for (int i = 0; i < h + 1; ++i) {
        for (int j = 0; j < w; ++j) {
          sumList[i][j + 1] = sumList[i][j + 1].binaryOperation(sumList[i][j]);
        }
      }
    }
    constexpr S get(int y, int x) { return sumList[y + 1][x + 1].m_val; }
    constexpr S get(int y1, int x1, int y2, int x2) {
      if (y2 < y1 || x2 < x1) { return Group().m_val; }
      x1 = std::max(x1, 0);
      y1 = std::max(y1, 0);
      y2 = std::min(y2, h - 1);
      x2 = std::min(x2, w - 1);
      return sumList[y2 + 1][x2 + 1]
          .binaryOperation(sumList[y1][x1])
          .binaryOperation(sumList[y2 + 1][x1].inverse())
          .binaryOperation(sumList[y1][x2 + 1].inverse())
          .m_val;
    }
  };

}  // namespace mtd

Back to top page