2D disjoint sparse table (tools/disjoint_sparse_table_2d.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2025-02-10 20:05:30+09:00
• Include: #include "tools/disjoint_sparse_table_2d.hpp"

It is a data structure which can return $\prod_{d \leq i < u} \prod_{l \leq j < r} A_{i, j}$ under a given monoid for given $d, u, l, r$ in $\langle O(HW \log H \log W), 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

template <typename Range>
disjoint_sparse_table_2d<M> dst(Range A);

It constructs a data structure which can return $\prod_{d \leq i < u} \prod_{l \leq j < r} A_{i, j}$ under a given monoid for given $d, u, l, r$ in $\langle O(HW \log H \log W), 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 M::T.
• For all $a$ in typename M::T, $b$ in typename M::T and $c$ in typename M::T, M::op(M::op(a, b), c) $=$ M::op(a, M::op(b, c)).
• For all $a$ in typename M::T, M::op(M::e(), a) $=$ M::op(a, M::e()) $=$ a.
• For all $a$ in typename M::T and $b$ in typename M::T, M::op(a, b) $=$ M::op(b, a).

Time Complexity

• $O(HW \log H \log W)$

height

std::size_t dst.height();

It returns $H$.

Constraints

• None

Time Complexity

• $O(1)$

width

std::size_t dst.width();

It returns $W$.

Constraints

• None

Time Complexity

• $O(1)$

prod

typename M::T dst.prod(std::size_t d, std::size_t u, std::size_t l, std::size_t r);

It returns $\prod_{d \leq i < u} \prod_{l \leq j < r} A_{i, j}$ under the monoid <M>.

Constraints

• $0 \leq d \leq u \leq H$
• $0 \leq l \leq r \leq W$

Time Complexity

• $O(1)$

Depends on

• Bit width required to represent a given integer (tools/bit_width.hpp)
• $\left\lceil \log_2(x) \right\rceil$ (tools/ceil_log2.hpp)
• $\left\lfloor \log_2(x) \right\rfloor$ (tools/floor_log2.hpp)
• std::is_integral extended for tools::int128_t and tools::uint128_t (tools/is_integral.hpp)
• std::is_signed extended for tools::int128_t and tools::uint128_t (tools/is_signed.hpp)
• std::make_unsigned extended for tools::int128_t and tools::uint128_t (tools/make_unsigned.hpp)
• $2^x$ (tools/pow2.hpp)

Verified with

• tests/disjoint_sparse_table_2d.test.cpp

Code

#ifndef TOOLS_DISJOINT_SPARSE_TABLE_2D_HPP
#define TOOLS_DISJOINT_SPARSE_TABLE_2D_HPP

#include <vector>
#include <cstddef>
#include <algorithm>
#include <iterator>
#include <cassert>
#include "tools/ceil_log2.hpp"
#include "tools/pow2.hpp"
#include "tools/floor_log2.hpp"

namespace tools {
  template <typename M>
  class disjoint_sparse_table_2d {
  private:
    using T = typename M::T;
    ::std::vector<::std::vector<T>> m_value;
    ::std::size_t m_height;
    ::std::size_t m_width;
    ::std::size_t m_hcapacity;
    ::std::size_t m_wcapacity;

  public:
    disjoint_sparse_table_2d() = default;
    disjoint_sparse_table_2d(const ::tools::disjoint_sparse_table_2d<M>&) = default;
    disjoint_sparse_table_2d(::tools::disjoint_sparse_table_2d<M>&&) = default;
    ~disjoint_sparse_table_2d() = default;
    ::tools::disjoint_sparse_table_2d<M>& operator=(const ::tools::disjoint_sparse_table_2d<M>&) = default;
    ::tools::disjoint_sparse_table_2d<M>& operator=(::tools::disjoint_sparse_table_2d<M>&&) = default;

    template <typename Range>
    explicit disjoint_sparse_table_2d(const Range& range) {
      const auto begin = ::std::begin(range);
      const auto end = ::std::end(range);
      this->m_height = ::std::distance(begin, end);
      this->m_width = this->m_height == 0 ? 0 : ::std::distance(::std::begin(*begin), ::std::end(*begin));
      assert(::std::all_of(begin, end, [&](const auto& row) { return static_cast<::std::size_t>(::std::distance(::std::begin(row), ::std::end(row))) == this->m_width; }));

      const auto hdepth = this->m_height <= 1 ? this->m_height : ::tools::ceil_log2(this->m_height);
      const auto wdepth = this->m_width <= 1 ? this->m_width : ::tools::ceil_log2(this->m_width);
      this->m_hcapacity = this->m_height <= 1 ? this->m_height : ::tools::pow2(hdepth);
      this->m_wcapacity = this->m_width <= 1 ? this->m_width : ::tools::pow2(wdepth);

      const auto construct_horizontal_dst = [&](::std::vector<T>& row) {
        row.resize(wdepth * this->m_wcapacity);
        ::std::fill(row.begin() + this->m_width, row.begin() + this->m_wcapacity, M::e());

        for (::std::size_t d = 1; d < wdepth; ++d) {
          const ::std::size_t offset = d * this->m_wcapacity;
          for (::std::size_t m = ::tools::pow2(d); m < this->m_wcapacity; m += ::tools::pow2(d + 1)) {
            row[offset + (m - 1)] = row[m - 1];
            row[offset + m] = row[m];
            for (::std::size_t l = m - 1; l --> m - ::tools::pow2(d);) {
              row[offset + l] = M::op(row[l], row[offset + (l + 1)]);
            }
            for (::std::size_t r = m + 2; r <= m + ::tools::pow2(d); ++r) {
              row[offset + (r - 1)] = M::op(row[offset + (r - 2)], row[r - 1]);
            }
          }
        }
      };

      this->m_value.resize(hdepth * this->m_hcapacity);
      for (auto& row : this->m_value) {
        row.reserve(wdepth * this->m_wcapacity);
      }
      for (::std::size_t h = 0; h < this->m_height; ++h) {
        ::std::copy(::std::begin(begin[h]), ::std::end(begin[h]), ::std::back_inserter(this->m_value[h]));
        construct_horizontal_dst(this->m_value[h]);
      }
      for (::std::size_t h = this->m_height; h < this->m_hcapacity; ++h) {
        this->m_value[h].resize(wdepth * this->m_wcapacity, M::e());
      }

      for (::std::size_t d = 1; d < hdepth; ++d) {
        const ::std::size_t offset = d * this->m_hcapacity;
        for (::std::size_t m = ::tools::pow2(d); m < this->m_hcapacity; m += ::tools::pow2(d + 1)) {
          ::std::copy(this->m_value[m - 1].begin(), this->m_value[m - 1].end(), ::std::back_inserter(this->m_value[offset + (m - 1)]));
          ::std::copy(this->m_value[m].begin(), this->m_value[m].end(), ::std::back_inserter(this->m_value[offset + m]));
          for (::std::size_t l = m - 1; l --> m - ::tools::pow2(d);) {
            for (::std::size_t w = 0; w < wdepth * this->m_wcapacity; ++w) {
              this->m_value[offset + l].push_back(M::op(this->m_value[l][w], this->m_value[offset + (l + 1)][w]));
            }
          }
          for (::std::size_t r = m + 2; r <= m + ::tools::pow2(d); ++r) {
            for (::std::size_t w = 0; w < wdepth * this->m_wcapacity; ++w) {
              this->m_value[offset + (r - 1)].push_back(M::op(this->m_value[offset + (r - 2)][w], this->m_value[r - 1][w]));
            }
          }
        }
      }
    }

    ::std::size_t height() const {
      return this->m_height;
    }
    ::std::size_t width() const {
      return this->m_width;
    }

    T prod(const ::std::size_t d, const ::std::size_t u, const ::std::size_t l, const ::std::size_t r) const {
      assert(d <= u && u <= this->m_height);
      assert(l <= r && r <= this->m_width);
      if (u - d == 0 || r - l == 0) {
        return M::e();
      } else if (u - d == 1 && r - l == 1) {
        return this->m_value[d][l];
      } else if (u - d == 1) {
        const ::std::size_t woffset = ::tools::floor_log2(l ^ (r - 1)) * this->m_wcapacity;
        return M::op(this->m_value[d][woffset + l], this->m_value[d][woffset + (r - 1)]);
      } else if (r - l == 1) {
        const ::std::size_t hoffset = ::tools::floor_log2(d ^ (u - 1)) * this->m_hcapacity;
        return M::op(this->m_value[hoffset + d][l], this->m_value[hoffset + (u - 1)][l]);
      } else {
        const ::std::size_t hoffset = ::tools::floor_log2(d ^ (u - 1)) * this->m_hcapacity;
        const ::std::size_t woffset = ::tools::floor_log2(l ^ (r - 1)) * this->m_wcapacity;
        return M::op(
          M::op(this->m_value[hoffset + d][woffset + l], this->m_value[hoffset + d][woffset + (r - 1)]),
          M::op(this->m_value[hoffset + (u - 1)][woffset + l], this->m_value[hoffset + (u - 1)][woffset + (r - 1)])
        );
      }
    }
  };
}

#endif

#line 1 "tools/disjoint_sparse_table_2d.hpp"



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



#line 1 "tools/bit_width.hpp"



#include <bit>
#line 6 "tools/bit_width.hpp"
#include <type_traits>
#line 1 "tools/is_integral.hpp"



#line 5 "tools/is_integral.hpp"

namespace tools {
  template <typename T>
  struct is_integral : ::std::is_integral<T> {};

  template <typename T>
  inline constexpr bool is_integral_v = ::tools::is_integral<T>::value;
}


#line 1 "tools/is_signed.hpp"



#line 5 "tools/is_signed.hpp"

namespace tools {
  template <typename T>
  struct is_signed : ::std::is_signed<T> {};

  template <typename T>
  inline constexpr bool is_signed_v = ::tools::is_signed<T>::value;
}


#line 1 "tools/make_unsigned.hpp"



#line 5 "tools/make_unsigned.hpp"

namespace tools {
  template <typename T>
  struct make_unsigned : ::std::make_unsigned<T> {};

  template <typename T>
  using make_unsigned_t = typename ::tools::make_unsigned<T>::type;
}


#line 10 "tools/bit_width.hpp"

namespace tools {
  template <typename T>
  constexpr int bit_width(T) noexcept;

  template <typename T>
  constexpr int bit_width(const T x) noexcept {
    static_assert(::tools::is_integral_v<T> && !::std::is_same_v<::std::remove_cv_t<T>, bool>);
    if constexpr (::tools::is_signed_v<T>) {
      assert(x >= 0);
      return ::tools::bit_width<::tools::make_unsigned_t<T>>(x);
    } else {
      return ::std::bit_width(x);
    }
  }
}


#line 6 "tools/ceil_log2.hpp"

namespace tools {
  template <typename T>
  constexpr T ceil_log2(T x) noexcept {
    assert(x > 0);
    return ::tools::bit_width(x - 1);
  }
}


#line 1 "tools/pow2.hpp"



#line 6 "tools/pow2.hpp"

namespace tools {

  template <typename T, typename ::std::enable_if<::std::is_unsigned<T>::value, ::std::nullptr_t>::type = nullptr>
  constexpr T pow2(const T x) {
    return static_cast<T>(1) << x;
  }

  template <typename T, typename ::std::enable_if<::std::is_signed<T>::value, ::std::nullptr_t>::type = nullptr>
  constexpr T pow2(const T x) {
    return static_cast<T>(static_cast<typename ::std::make_unsigned<T>::type>(1) << static_cast<typename ::std::make_unsigned<T>::type>(x));
  }
}


#line 1 "tools/floor_log2.hpp"



#line 6 "tools/floor_log2.hpp"

namespace tools {
  template <typename T>
  constexpr T floor_log2(T x) noexcept {
    assert(x > 0);
    return ::tools::bit_width(x) - 1;
  }
}


#line 12 "tools/disjoint_sparse_table_2d.hpp"

namespace tools {
  template <typename M>
  class disjoint_sparse_table_2d {
  private:
    using T = typename M::T;
    ::std::vector<::std::vector<T>> m_value;
    ::std::size_t m_height;
    ::std::size_t m_width;
    ::std::size_t m_hcapacity;
    ::std::size_t m_wcapacity;

  public:
    disjoint_sparse_table_2d() = default;
    disjoint_sparse_table_2d(const ::tools::disjoint_sparse_table_2d<M>&) = default;
    disjoint_sparse_table_2d(::tools::disjoint_sparse_table_2d<M>&&) = default;
    ~disjoint_sparse_table_2d() = default;
    ::tools::disjoint_sparse_table_2d<M>& operator=(const ::tools::disjoint_sparse_table_2d<M>&) = default;
    ::tools::disjoint_sparse_table_2d<M>& operator=(::tools::disjoint_sparse_table_2d<M>&&) = default;

    template <typename Range>
    explicit disjoint_sparse_table_2d(const Range& range) {
      const auto begin = ::std::begin(range);
      const auto end = ::std::end(range);
      this->m_height = ::std::distance(begin, end);
      this->m_width = this->m_height == 0 ? 0 : ::std::distance(::std::begin(*begin), ::std::end(*begin));
      assert(::std::all_of(begin, end, [&](const auto& row) { return static_cast<::std::size_t>(::std::distance(::std::begin(row), ::std::end(row))) == this->m_width; }));

      const auto hdepth = this->m_height <= 1 ? this->m_height : ::tools::ceil_log2(this->m_height);
      const auto wdepth = this->m_width <= 1 ? this->m_width : ::tools::ceil_log2(this->m_width);
      this->m_hcapacity = this->m_height <= 1 ? this->m_height : ::tools::pow2(hdepth);
      this->m_wcapacity = this->m_width <= 1 ? this->m_width : ::tools::pow2(wdepth);

      const auto construct_horizontal_dst = [&](::std::vector<T>& row) {
        row.resize(wdepth * this->m_wcapacity);
        ::std::fill(row.begin() + this->m_width, row.begin() + this->m_wcapacity, M::e());

        for (::std::size_t d = 1; d < wdepth; ++d) {
          const ::std::size_t offset = d * this->m_wcapacity;
          for (::std::size_t m = ::tools::pow2(d); m < this->m_wcapacity; m += ::tools::pow2(d + 1)) {
            row[offset + (m - 1)] = row[m - 1];
            row[offset + m] = row[m];
            for (::std::size_t l = m - 1; l --> m - ::tools::pow2(d);) {
              row[offset + l] = M::op(row[l], row[offset + (l + 1)]);
            }
            for (::std::size_t r = m + 2; r <= m + ::tools::pow2(d); ++r) {
              row[offset + (r - 1)] = M::op(row[offset + (r - 2)], row[r - 1]);
            }
          }
        }
      };

      this->m_value.resize(hdepth * this->m_hcapacity);
      for (auto& row : this->m_value) {
        row.reserve(wdepth * this->m_wcapacity);
      }
      for (::std::size_t h = 0; h < this->m_height; ++h) {
        ::std::copy(::std::begin(begin[h]), ::std::end(begin[h]), ::std::back_inserter(this->m_value[h]));
        construct_horizontal_dst(this->m_value[h]);
      }
      for (::std::size_t h = this->m_height; h < this->m_hcapacity; ++h) {
        this->m_value[h].resize(wdepth * this->m_wcapacity, M::e());
      }

      for (::std::size_t d = 1; d < hdepth; ++d) {
        const ::std::size_t offset = d * this->m_hcapacity;
        for (::std::size_t m = ::tools::pow2(d); m < this->m_hcapacity; m += ::tools::pow2(d + 1)) {
          ::std::copy(this->m_value[m - 1].begin(), this->m_value[m - 1].end(), ::std::back_inserter(this->m_value[offset + (m - 1)]));
          ::std::copy(this->m_value[m].begin(), this->m_value[m].end(), ::std::back_inserter(this->m_value[offset + m]));
          for (::std::size_t l = m - 1; l --> m - ::tools::pow2(d);) {
            for (::std::size_t w = 0; w < wdepth * this->m_wcapacity; ++w) {
              this->m_value[offset + l].push_back(M::op(this->m_value[l][w], this->m_value[offset + (l + 1)][w]));
            }
          }
          for (::std::size_t r = m + 2; r <= m + ::tools::pow2(d); ++r) {
            for (::std::size_t w = 0; w < wdepth * this->m_wcapacity; ++w) {
              this->m_value[offset + (r - 1)].push_back(M::op(this->m_value[offset + (r - 2)][w], this->m_value[r - 1][w]));
            }
          }
        }
      }
    }

    ::std::size_t height() const {
      return this->m_height;
    }
    ::std::size_t width() const {
      return this->m_width;
    }

    T prod(const ::std::size_t d, const ::std::size_t u, const ::std::size_t l, const ::std::size_t r) const {
      assert(d <= u && u <= this->m_height);
      assert(l <= r && r <= this->m_width);
      if (u - d == 0 || r - l == 0) {
        return M::e();
      } else if (u - d == 1 && r - l == 1) {
        return this->m_value[d][l];
      } else if (u - d == 1) {
        const ::std::size_t woffset = ::tools::floor_log2(l ^ (r - 1)) * this->m_wcapacity;
        return M::op(this->m_value[d][woffset + l], this->m_value[d][woffset + (r - 1)]);
      } else if (r - l == 1) {
        const ::std::size_t hoffset = ::tools::floor_log2(d ^ (u - 1)) * this->m_hcapacity;
        return M::op(this->m_value[hoffset + d][l], this->m_value[hoffset + (u - 1)][l]);
      } else {
        const ::std::size_t hoffset = ::tools::floor_log2(d ^ (u - 1)) * this->m_hcapacity;
        const ::std::size_t woffset = ::tools::floor_log2(l ^ (r - 1)) * this->m_wcapacity;
        return M::op(
          M::op(this->m_value[hoffset + d][woffset + l], this->m_value[hoffset + d][woffset + (r - 1)]),
          M::op(this->m_value[hoffset + (u - 1)][woffset + l], this->m_value[hoffset + (u - 1)][woffset + (r - 1)])
        );
      }
    }
  };
}

Back to top page