2D cumulative sum (tools/cumsum2d.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2024-10-05 00:25:57+09:00
• Include: #include "tools/cumsum2d.hpp"

It is a data structure which can return $\sum_{r = r_1}^{r_2 - 1} \sum_{c = c_1}^{c_2 - 1} A_{r,c}$ for given $r_1, r_2, c_1, c_2$ in $\langle O(HW), O(1) \rangle$ time, where $H$ is the number of rows of $A$, and $W$ is the number of columns of $A$.

License

• CC0

Author

• anqooqie

Constructor

(1)
template <typename Range>
cumsum2d<T> cumsum(Range A);

(2)
template <typename Range>
cumsum2d<G> cumsum(Range A);

• (1)
  • It is identical to cumsum2d<tools::group::plus<T>> cumsum(A);.
• (2)
  • It constructs a data structure which can return $\sum_{r = r_1}^{r_2 - 1} \sum_{c = c_1}^{c_2 - 1} A_{r,c}$ for a given $r_1, r_2, c_1, c_2$ in $\langle O(HW), O(1) \rangle$ time, where $H$ is the number of rows of $A$, and $W$ is the number of columns of $A$.

Constraints

• std::begin(range) and std::end(range) are compilable and has the same type.
• std::begin(*std::begin(range)) and std::end(*std::begin(range)) are compilable and has the same type.
• The type of *std::begin(*std::begin(range)) is typename G::T.
• For all $a$ in typename G::T, $b$ in typename G::T and $c$ in typename G::T, G::op(G::op(a, b), c) $=$ G::op(a, G::op(b, c)).
• For all $a$ in typename G::T, G::op(G::e(), a) $=$ G::op(a, G::e()) $=$ a.
• For all $a$ in typename G::T, G::op(G::inv(a), a) $=$ G::op(a, G::inv(a)) $=$ G::e().

Time Complexity

• $O(HW)$ where $H$ is the number of rows of $A$ and $W$ is the number of columns of $A$

query

typename G::T cumsum.query(std::size_t r1, std::size_t r2, std::size_t c1, std::size_t c2);

It returns $\sum_{r = r_1}^{r_2 - 1} \sum_{c = c_1}^{c_2 - 1} A_{r,c}$.

Constraints

• $0 \leq r_1 \leq r_2 \leq H$
• $0 \leq c_1 \leq c_2 \leq W$

Time Complexity

• $O(1)$

Depends on

• Typical groups (tools/group.hpp)
• Check whether T is a group (tools/is_group.hpp)

Verified with

• tests/bigdecimal/cast_to_long_long.test.cpp
• tests/cartesian_tree/interval.test.cpp
• tests/cumsum2d.test.cpp

Code

#ifndef TOOLS_CUMSUM2D_HPP
#define TOOLS_CUMSUM2D_HPP

#include <type_traits>
#include <cstddef>
#include <vector>
#include <iterator>
#include <algorithm>
#include <cassert>
#include "tools/is_group.hpp"
#include "tools/group.hpp"

namespace tools {

  template <typename X>
  class cumsum2d {
  private:
    using G = ::std::conditional_t<::tools::is_group_v<X>, X, tools::group::plus<X>>;
    using T = typename G::T;
    ::std::size_t height;
    ::std::size_t width;
    ::std::vector<T> preprocessed;

  public:
    template <typename Range>
    explicit cumsum2d(const Range& range) {
      const auto begin = ::std::begin(range);
      const auto end = ::std::end(range);
      this->height = ::std::distance(begin, end);
      this->width = this->height == 0 ? 0 : ::std::distance(::std::begin(*begin), ::std::end(*begin));
      this->preprocessed.reserve((this->height + 1) * (this->width + 1));
      ::std::fill_n(::std::back_inserter(this->preprocessed), (this->height + 1) * (this->width + 1), G::e());

      {
        auto it1 = begin;
        for (::std::size_t y = 0; y < this->height; ++y, ++it1) {
          auto it2 = ::std::begin(*it1);
          for (::std::size_t x = 0; x < this->width; ++x, ++it2) {
            this->preprocessed[(y + 1) * (this->width + 1) + (x + 1)] = G::op(this->preprocessed[(y + 1) * (this->width + 1) + x], *it2);
          }
        }
      }
      for (::std::size_t x = 0; x < this->width; ++x) {
        for (::std::size_t y = 0; y < this->height; ++y) {
          this->preprocessed[(y + 1) * (this->width + 1) + (x + 1)] = G::op(this->preprocessed[y * (this->width + 1) + (x + 1)], this->preprocessed[(y + 1) * (this->width + 1) + (x + 1)]);
        }
      }
    }

    T query(const ::std::size_t y1, const ::std::size_t y2, const ::std::size_t x1, const ::std::size_t x2) const {
      assert(y1 <= y2 && y2 <= this->height);
      assert(x1 <= x2 && x2 <= this->width);
      return G::op(
        G::op(
          G::op(
            this->preprocessed[y2 * (this->width + 1) + x2],
            G::inv(this->preprocessed[y2 * (this->width + 1) + x1])
          ),
          G::inv(this->preprocessed[y1 * (this->width + 1) + x2])
        ),
        this->preprocessed[y1 * (this->width + 1) + x1]
      );
    }
  };
}

#endif

#line 1 "tools/cumsum2d.hpp"



#include <type_traits>
#include <cstddef>
#include <vector>
#include <iterator>
#include <algorithm>
#include <cassert>
#line 1 "tools/is_group.hpp"



#line 5 "tools/is_group.hpp"
#include <utility>

namespace tools {

  template <typename G, typename = void>
  struct is_group : ::std::false_type {};

  template <typename G>
  struct is_group<G, ::std::enable_if_t<
    ::std::is_same_v<typename G::T, decltype(G::op(::std::declval<typename G::T>(), ::std::declval<typename G::T>()))> &&
    ::std::is_same_v<typename G::T, decltype(G::e())> &&
    ::std::is_same_v<typename G::T, decltype(G::inv(::std::declval<typename G::T>()))>
  , void>> : ::std::true_type {};

  template <typename G>
  inline constexpr bool is_group_v = ::tools::is_group<G>::value;
}


#line 1 "tools/group.hpp"



namespace tools {
  namespace group {
    template <typename G>
    struct plus {
      using T = G;
      static T op(const T& lhs, const T& rhs) {
        return lhs + rhs;
      }
      static T e() {
        return T(0);
      }
      static T inv(const T& v) {
        return -v;
      }
    };

    template <typename G>
    struct multiplies {
      using T = G;
      static T op(const T& lhs, const T& rhs) {
        return lhs * rhs;
      }
      static T e() {
        return T(1);
      }
      static T inv(const T& v) {
        return e() / v;
      }
    };

    template <typename G>
    struct bit_xor {
      using T = G;
      static T op(const T& lhs, const T& rhs) {
        return lhs ^ rhs;
      }
      static T e() {
        return T(0);
      }
      static T inv(const T& v) {
        return v;
      }
    };
  }
}


#line 12 "tools/cumsum2d.hpp"

namespace tools {

  template <typename X>
  class cumsum2d {
  private:
    using G = ::std::conditional_t<::tools::is_group_v<X>, X, tools::group::plus<X>>;
    using T = typename G::T;
    ::std::size_t height;
    ::std::size_t width;
    ::std::vector<T> preprocessed;

  public:
    template <typename Range>
    explicit cumsum2d(const Range& range) {
      const auto begin = ::std::begin(range);
      const auto end = ::std::end(range);
      this->height = ::std::distance(begin, end);
      this->width = this->height == 0 ? 0 : ::std::distance(::std::begin(*begin), ::std::end(*begin));
      this->preprocessed.reserve((this->height + 1) * (this->width + 1));
      ::std::fill_n(::std::back_inserter(this->preprocessed), (this->height + 1) * (this->width + 1), G::e());

      {
        auto it1 = begin;
        for (::std::size_t y = 0; y < this->height; ++y, ++it1) {
          auto it2 = ::std::begin(*it1);
          for (::std::size_t x = 0; x < this->width; ++x, ++it2) {
            this->preprocessed[(y + 1) * (this->width + 1) + (x + 1)] = G::op(this->preprocessed[(y + 1) * (this->width + 1) + x], *it2);
          }
        }
      }
      for (::std::size_t x = 0; x < this->width; ++x) {
        for (::std::size_t y = 0; y < this->height; ++y) {
          this->preprocessed[(y + 1) * (this->width + 1) + (x + 1)] = G::op(this->preprocessed[y * (this->width + 1) + (x + 1)], this->preprocessed[(y + 1) * (this->width + 1) + (x + 1)]);
        }
      }
    }

    T query(const ::std::size_t y1, const ::std::size_t y2, const ::std::size_t x1, const ::std::size_t x2) const {
      assert(y1 <= y2 && y2 <= this->height);
      assert(x1 <= x2 && x2 <= this->width);
      return G::op(
        G::op(
          G::op(
            this->preprocessed[y2 * (this->width + 1) + x2],
            G::inv(this->preprocessed[y2 * (this->width + 1) + x1])
          ),
          G::inv(this->preprocessed[y1 * (this->width + 1) + x2])
        ),
        this->preprocessed[y1 * (this->width + 1) + x1]
      );
    }
  };
}

Back to top page