Disjoint sparse table (tools/disjoint_sparse_table.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.hpp"

It is a data structure which can return $\prod_{l \leq i < r} a_i$ under a given monoid in $\langle O(N \log N), O(1) \rangle$ time.

License

• CC0

Author

• anqooqie

Constructor

template <typename InputIterator>
disjoint_sparse_table<M> table(InputIterator begin, InputIterator end);

It takes a sequence $(a_1, a_2, \ldots, a_N)$, and constructs a data structure which can return $\prod_{l \leq i < r} a_i$ under a given monoid $M$.

Constraints

• 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.

Time Complexity

• $O(N \log N)$

size

std::size_t table.size();

It returns $N$.

Constraints

• None

Time Complexity

• $O(1)$

prod

typename M::T table.prod(std::size_t l, std::size_t r);

It returns $\prod_{l \leq i < r} a_i$ under the monoid $M$.

Constraints

• $0 \leq l \leq r \leq N$

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.test.cpp

Code

#ifndef TOOLS_DISJOINT_SPARSE_TABLE_HPP
#define TOOLS_DISJOINT_SPARSE_TABLE_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 {
  private:
    using T = typename M::T;
    ::std::vector<T> m_value;
    ::std::size_t m_size;
    ::std::size_t m_capacity;
    ::std::size_t m_height;

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

    template <typename InputIterator>
    disjoint_sparse_table(const InputIterator& begin, const InputIterator& end) {
      ::std::copy(begin, end, ::std::back_inserter(this->m_value));
      this->m_size = this->m_value.size();
      this->m_height = this->m_size <= 1 ? this->m_size : ::tools::ceil_log2(this->m_size);
      this->m_capacity = this->m_size <= 1 ? this->m_size : ::tools::pow2(this->m_height);
      this->m_value.resize(this->m_height * this->m_capacity);
      ::std::fill(this->m_value.begin() + this->m_size, this->m_value.begin() + this->m_capacity, M::e());

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

    ::std::size_t size() const {
      return this->m_size;
    }

    T prod(const ::std::size_t l, const ::std::size_t r) const {
      assert(l <= r && r <= this->m_size);
      if (r - l == 0) {
        return M::e();
      } else if (r - l == 1) {
        return this->m_value[l];
      } else {
        const ::std::size_t offset = ::tools::floor_log2(l ^ (r - 1)) * this->m_capacity;
        return M::op(this->m_value[offset + l], this->m_value[offset + (r - 1)]);
      }
    }
  };
}

#endif

#line 1 "tools/disjoint_sparse_table.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.hpp"

namespace tools {
  template <typename M>
  class disjoint_sparse_table {
  private:
    using T = typename M::T;
    ::std::vector<T> m_value;
    ::std::size_t m_size;
    ::std::size_t m_capacity;
    ::std::size_t m_height;

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

    template <typename InputIterator>
    disjoint_sparse_table(const InputIterator& begin, const InputIterator& end) {
      ::std::copy(begin, end, ::std::back_inserter(this->m_value));
      this->m_size = this->m_value.size();
      this->m_height = this->m_size <= 1 ? this->m_size : ::tools::ceil_log2(this->m_size);
      this->m_capacity = this->m_size <= 1 ? this->m_size : ::tools::pow2(this->m_height);
      this->m_value.resize(this->m_height * this->m_capacity);
      ::std::fill(this->m_value.begin() + this->m_size, this->m_value.begin() + this->m_capacity, M::e());

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

    ::std::size_t size() const {
      return this->m_size;
    }

    T prod(const ::std::size_t l, const ::std::size_t r) const {
      assert(l <= r && r <= this->m_size);
      if (r - l == 0) {
        return M::e();
      } else if (r - l == 1) {
        return this->m_value[l];
      } else {
        const ::std::size_t offset = ::tools::floor_log2(l ^ (r - 1)) * this->m_capacity;
        return M::op(this->m_value[offset + l], this->m_value[offset + (r - 1)]);
      }
    }
  };
}

Back to top page