Sparse table
(include/data_structure/sparse_table.hpp)

View this file on GitHub
Last update: 2021-08-11 13:38:32+09:00
Include: #include "include/data_structure/sparse_table.hpp"

要素が変化しない配列の情報を格納し、結合法則と冪等性を満たす演算(最小値, 最大値, 最小公倍数, 最大公約数等を求める演算)の区間積を高速に求めることができるデータ構造である sparse_table クラスが定義されています。

コンストラクタ

std::vector<int> v {1, 2, 3, 4, 5, 6};
const auto lcm = [](const int x, const int y) constexpr -> int { return std::lcm(x, y); };

lib::sparse_table t1(v, lcm);  // 1.
lib::sparse_table<long long, decltype(lcm)> t2(v, lcm);  // 2.

配列と関数オブジェクトを受け取って sparse table を構築します。
最小公倍数のように関数が返す値が配列の要素よりも大きくオーバーフローの恐れがある場合等には(より大きな値を表現できる)要素の型を明示して構築をすることができます。

メンバ関数

`size()`

配列の要素数を返します。

`get(i)`

$i$ 番目 (0-indexed) の要素の値を返します。

`query(l, r)`

半開区間 $[l, r)$ (0-indexed) に含まれる要素に対して演算を作用させた結果(区間積)を返します。

Verified with

test/data_structure/sparse_table/1.test.cpp

Code

//! @file sparse_table.hpp
//! @details Provide a data structure to calculate interval products of associative and idempotent operations.

#ifndef CP_LIBRARY_SPARSE_TABLE_HPP
#define CP_LIBRARY_SPARSE_TABLE_HPP

#include <cassert>
#include <limits>
#include <type_traits>
#include <vector>

#ifndef CP_LIBRARY_ASSERT
//! @brief Assert macro
#  define CP_LIBRARY_ASSERT(...) assert(__VA_ARGS__)
#  define CP_LIBRARY_ASSERT_NOT_DEFINED
#endif

namespace lib {

namespace internal::sparse_table_hpp {
  [[nodiscard]] int int_log2(const int n) {
    return std::numeric_limits<int>::digits - __builtin_clz(n);
  }
}  // namespace internal::sparse_table_hpp

//! @brief data structure to calculate interval products of associative and idempotent operations (for static array)
//! @tparam Elem element type (deduced from constructor's parameters but can be set manually if needed)
//! @tparam Func functor type (deduced from constructor's parameters but has to be specified if you set Elem manually)
template <typename Elem, typename Func>
class sparse_table {
private:
  const int length;
  const Func& binary_op;
  std::vector<std::vector<Elem>> table;

public:
  //! @brief Construct a sparse table from source container
  //! @tparam Container container type (deduced from parameter)
  //! @param src source container
  //! @param binary_op_functor functor (must be associative & idempotent)
  //! @note Time complexity: O(N log N) where N = size(src)
  template <typename Container>
  sparse_table(const Container& src, const Func& binary_op_functor)
      : length(static_cast<int>(std::size(src))), binary_op(binary_op_functor) {
    const int M = internal::sparse_table_hpp::int_log2(length) + 1;

    table = std::vector(length, std::vector<Elem>(M));

    for (int i = 0; i < length; ++i)
      table[i][0] = src[i];
    for (int j = 1; j < M; ++j)
      for (int i = 0; i + (1 << j) <= length; ++i)
        table[i][j] = binary_op(table[i][j - 1], table[i + (1 << (j - 1))][j - 1]);
  }

  //! @return Vector length
  [[nodiscard]] int size() const noexcept {
    return length;
  }

  //! @brief Get the value of the index-th element.
  //! @param index index (0-indexed)
  [[nodiscard]] Elem get(const int index) const {
    return table[index][0];
  }

  //! @param left lower limit of interval (0-indexed)
  //! @param right upper limit of interval (0-indexed)
  //! @return product of the elements of an interval [left, right) (half-open interval)
  //! @note Time complexity: O(1)
  [[nodiscard]] Elem query(const int left, const int right) const {
    CP_LIBRARY_ASSERT(0 <= left && left < right && right <= length);
    const int j = internal::sparse_table_hpp::int_log2(right - left);
    return binary_op(table[left][j], table[right - (1 << j)][j]);
  }
};

//! @brief Deduction guide
template <typename Container, typename Func>
sparse_table(const Container&, const Func&)
  -> sparse_table<std::decay_t<decltype(*std::begin(std::declval<Container>()))>, Func>;

}  // namespace lib

#ifdef CP_LIBRARY_ASSERT_NOT_DEFINED
#  undef CP_LIBRARY_ASSERT
#  undef CP_LIBRARY_ASSERT_NOT_DEFINED
#endif

#endif  // CP_LIBRARY_SPARSE_TABLE_HPP

#line 1 "include/data_structure/sparse_table.hpp"

//! @file sparse_table.hpp
//! @details Provide a data structure to calculate interval products of associative and idempotent operations.

#ifndef CP_LIBRARY_SPARSE_TABLE_HPP
#define CP_LIBRARY_SPARSE_TABLE_HPP

#include <cassert>
#include <limits>
#include <type_traits>
#include <vector>

#ifndef CP_LIBRARY_ASSERT
//! @brief Assert macro
#  define CP_LIBRARY_ASSERT(...) assert(__VA_ARGS__)
#  define CP_LIBRARY_ASSERT_NOT_DEFINED
#endif

namespace lib {

namespace internal::sparse_table_hpp {
  [[nodiscard]] int int_log2(const int n) {
    return std::numeric_limits<int>::digits - __builtin_clz(n);
  }
}  // namespace internal::sparse_table_hpp

//! @brief data structure to calculate interval products of associative and idempotent operations (for static array)
//! @tparam Elem element type (deduced from constructor's parameters but can be set manually if needed)
//! @tparam Func functor type (deduced from constructor's parameters but has to be specified if you set Elem manually)
template <typename Elem, typename Func>
class sparse_table {
private:
  const int length;
  const Func& binary_op;
  std::vector<std::vector<Elem>> table;

public:
  //! @brief Construct a sparse table from source container
  //! @tparam Container container type (deduced from parameter)
  //! @param src source container
  //! @param binary_op_functor functor (must be associative & idempotent)
  //! @note Time complexity: O(N log N) where N = size(src)
  template <typename Container>
  sparse_table(const Container& src, const Func& binary_op_functor)
      : length(static_cast<int>(std::size(src))), binary_op(binary_op_functor) {
    const int M = internal::sparse_table_hpp::int_log2(length) + 1;

    table = std::vector(length, std::vector<Elem>(M));

    for (int i = 0; i < length; ++i)
      table[i][0] = src[i];
    for (int j = 1; j < M; ++j)
      for (int i = 0; i + (1 << j) <= length; ++i)
        table[i][j] = binary_op(table[i][j - 1], table[i + (1 << (j - 1))][j - 1]);
  }

  //! @return Vector length
  [[nodiscard]] int size() const noexcept {
    return length;
  }

  //! @brief Get the value of the index-th element.
  //! @param index index (0-indexed)
  [[nodiscard]] Elem get(const int index) const {
    return table[index][0];
  }

  //! @param left lower limit of interval (0-indexed)
  //! @param right upper limit of interval (0-indexed)
  //! @return product of the elements of an interval [left, right) (half-open interval)
  //! @note Time complexity: O(1)
  [[nodiscard]] Elem query(const int left, const int right) const {
    CP_LIBRARY_ASSERT(0 <= left && left < right && right <= length);
    const int j = internal::sparse_table_hpp::int_log2(right - left);
    return binary_op(table[left][j], table[right - (1 << j)][j]);
  }
};

//! @brief Deduction guide
template <typename Container, typename Func>
sparse_table(const Container&, const Func&)
  -> sparse_table<std::decay_t<decltype(*std::begin(std::declval<Container>()))>, Func>;

}  // namespace lib

#ifdef CP_LIBRARY_ASSERT_NOT_DEFINED
#  undef CP_LIBRARY_ASSERT
#  undef CP_LIBRARY_ASSERT_NOT_DEFINED
#endif

#endif  // CP_LIBRARY_SPARSE_TABLE_HPP

Sparse table (include/data_structure/sparse_table.hpp)