algorithm-dev

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub today2098/algorithm-dev

:heavy_check_mark: Sparse Table
(algorithm/DataStructure/SegmentTree/sparse_table.hpp)

概要

静的な要素列に対し，帯を成す演算（$\min, \max, \gcd, \operatorname{lcm}, \operatorname{bitwise-and}, \operatorname{bitwise-or}$ など）による任意の区間の要素の総積を求める．

ここで「帯 (band)」とは，次の性質を満たす組 $(S, \oplus: S \times S \rightarrow S)$ による代数的構造を指す（「冪等半群 (idempotent semigroup)」ともいう）．

  1. 結合律：$(a \oplus b) \oplus c = a \oplus (b \oplus c) \quad (\forall a, \forall b, \forall c \in S)$
  2. 冪等律：$a \oplus a = a \quad (\forall a \in S)$

アルゴリズムの計算量は，クエリ処理が $\mathcal{O}(1)$ と速い． 一方で，要素列の長さを $N$ とすると，テーブル構築の時間計算量および空間計算量に $\mathcal{O}(N \log N)$ を要する． クエリ数 $Q$ が $N$ より大きい場合に適している．

説明

algorithm::sparse_table::SparseTable

テンプレート引数 説明
IdempotentSemigroup モノイドの型．algorithm::algebra::Semigroup を想定している．
コンストラクタ 説明 計算量
SparseTable() デフォルトコンストラクタ．サイズゼロの SparseTable オブジェクトを構築する． -
SparseTable(first,last) コンストラクタ．イテレータ範囲 [first,last) の要素を用いて SparseTable オブジェクトを構築する． $\Theta(N \log N)$
SparseTable(il) 初期化子リスト il を受け取るコンストラクタ．SparseTable(il.begin(),il.end()) と等価． $\Theta(N \log N)$
メンバ関数 説明 計算量
x=size() 要素数 x を取得する． $\mathcal{O}(1)$
x=prod(k) k 番目の要素 x を取得する． $\mathcal{O}(1)$
x=prod(l,r) 区間 [l,r) の要素の総積 x を求める． $\mathcal{O}(1)$
x=prod_all() 区間全体の要素の総積 x を求める． $\mathcal{O}(1)$

参考

  1. “Band (algebra)”. Wikipedia. https://en.wikipedia.org/wiki/Band_(algebra).
  2. “半群”. Wikipedia. https://ja.wikipedia.org/wiki/半群.
  3. “冪等”. Wikipedia. https://ja.wikipedia.org/wiki/冪等.
  4. tookunn. “Sparse Tableを知ったので、忘れないように。”. Hatena Blog. https://tookunn.hatenablog.com/entry/2016/07/13/211148.
  5. “Sparse Table”. いかたこのたこつぼ. https://ikatakos.com/pot/programming_algorithm/data_structure/sparse_table.
  6. “特殊な半群”. 数学好きのすずめ. https://suzume-world.com/2021/05/02/特殊な半群/.

Depends on

Verified with

Code

#ifndef ALGORITHM_SPARSE_TABLE_HPP
#define ALGORITHM_SPARSE_TABLE_HPP 1

#include <cassert>
#include <initializer_list>
#include <iostream>
#include <iterator>
#include <vector>

#include "../../Math/Algebra/algebra.hpp"

namespace algorithm {

namespace sparse_table {

template <class IdempotentSemigroup>
class SparseTable {
public:
    using semigroup_type = IdempotentSemigroup;
    using value_type = semigroup_type::value_type;
    using size_type = std::size_t;

private:
    size_type m_sz;                                    // m_sz:=(要素数).
    std::vector<size_type> m_lg;                       // m_lg[x]:=floor(log2(x)).
    std::vector<std::vector<semigroup_type>> m_table;  // m_table[k][l]:=(区間[l,l+2^k)の総積).

public:
    // constructor. O(N log N).
    SparseTable() : m_sz(0), m_lg({0}), m_table({{}}) {}
    template <std::input_iterator InputIter>
    explicit SparseTable(InputIter first, InputIter last) : m_table(1, std::vector<semigroup_type>(first, last)) {
        m_sz = m_table[0].size();
        m_lg.assign(m_sz + 1, 0);
        for(size_type i = 2; i <= m_sz; ++i) m_lg[i] = m_lg[i >> 1] + 1;
        m_table.resize(m_lg[m_sz] + 1);
        for(size_type k = 1; k <= m_lg[m_sz]; ++k) {
            size_type n = m_sz - (1U << k) + 1;
            m_table[k].resize(n);
            for(size_type i = 0; i < n; ++i) m_table[k][i] = m_table[k - 1][i] * m_table[k - 1][i + (1U << (k - 1))];
        }
    }
    template <typename T>
    explicit SparseTable(std::initializer_list<T> il) : SparseTable(il.begin(), il.end()) {}

    // 要素数を取得する．
    size_type size() const { return m_sz; }
    // k番目の要素を取得する．O(1).
    value_type prod(size_type k) const {
        assert(k < size());
        return m_table[0][k].value();
    }
    // 区間[l,r)の要素の総積を求める．O(1).
    value_type prod(size_type l, size_type r) const {
        assert(l < r and r <= size());
        size_type k = m_lg[r - l];
        return (m_table[k][l] * m_table[k][r - (1U << k)]).value();
    }
    // 区間全体の要素の総積を求める．O(1).
    value_type prod_all() const {
        assert(size() > 0);
        return (m_table.back().front() * m_table.back().back()).value();
    }

    friend std::ostream &operator<<(std::ostream &os, const SparseTable &rhs) {
        os << "[\n";
        for(size_type k = 0; k <= rhs.m_lg.back(); ++k) {
            for(int i = 0, end = rhs.m_table[k].size(); i < end; ++i) os << (i == 0 ? "  [" : " ") << rhs.m_table[k][i];
            os << "]\n";
        }
        return os << "]";
    }
};

template <typename S>
using range_minimum_sparse_table = SparseTable<algebra::Semigroup<S, algebra::binary_operator::min<S>>>;

template <typename S>
using range_maximum_sparse_table = SparseTable<algebra::Semigroup<S, algebra::binary_operator::max<S>>>;

template <typename S>
using range_gcd_sparse_table = SparseTable<algebra::Semigroup<S, algebra::binary_operator::gcd<S>>>;

template <typename S>
using range_lcm_sparse_table = SparseTable<algebra::Semigroup<S, algebra::binary_operator::lcm<S>>>;

}  // namespace sparse_table

}  // namespace algorithm

#endif
#line 1 "algorithm/DataStructure/SegmentTree/sparse_table.hpp"



#include <cassert>
#include <initializer_list>
#include <iostream>
#include <iterator>
#include <vector>

#line 1 "algorithm/Math/Algebra/algebra.hpp"



#include <algorithm>
#line 6 "algorithm/Math/Algebra/algebra.hpp"
#include <limits>
#include <numeric>
#include <type_traits>
#include <utility>

namespace algorithm {

namespace algebra {

template <typename S>
class Set {
public:
    using value_type = S;

protected:
    value_type val;

public:
    constexpr Set() : val() {}
    constexpr Set(const value_type &val) : val(val) {}
    constexpr Set(value_type &&val) : val(std::move(val)) {}

    friend constexpr bool operator==(const Set &lhs, const Set &rhs) { return lhs.value() == rhs.value(); }
    friend std::istream &operator>>(std::istream &is, Set &rhs) { return is >> rhs.val; }
    friend std::ostream &operator<<(std::ostream &os, const Set &rhs) { return os << rhs.value(); }

    constexpr value_type value() const { return val; }
};

template <typename S, auto op>
class Semigroup : public Set<S> {
    static_assert(std::is_invocable_r<S, decltype(op), S, S>::value);

public:
    using base_type = Set<S>;
    using value_type = typename base_type::value_type;

    constexpr Semigroup() : base_type() {}
    constexpr Semigroup(const value_type &val) : base_type(val) {}
    constexpr Semigroup(value_type &&val) : base_type(std::move(val)) {}

    friend constexpr Semigroup operator*(const Semigroup &lhs, const Semigroup &rhs) { return Semigroup(op(lhs.value(), rhs.value())); }

    static constexpr auto get_op() { return op; }
};

template <typename S, auto op, auto e>
class Monoid : public Semigroup<S, op> {
    static_assert(std::is_invocable_r<S, decltype(e)>::value);

public:
    using base_type = Semigroup<S, op>;
    using value_type = typename base_type::value_type;

    constexpr Monoid() : base_type() {}
    constexpr Monoid(const value_type &val) : base_type(val) {}
    constexpr Monoid(value_type &&val) : base_type(std::move(val)) {}

    friend constexpr Monoid operator*(const Monoid &lhs, const Monoid &rhs) { return Monoid(op(lhs.value(), rhs.value())); }

    static constexpr auto get_e() { return e; }
    static constexpr Monoid one() { return Monoid(e()); }  // return identity element.
};

template <typename S, auto op, auto e, auto inverse>
class Group : public Monoid<S, op, e> {
    static_assert(std::is_invocable_r<S, decltype(inverse), S>::value);

public:
    using base_type = Monoid<S, op, e>;
    using value_type = typename base_type::value_type;

    constexpr Group() : base_type() {}
    constexpr Group(const value_type &val) : base_type(val) {}
    constexpr Group(value_type &&val) : base_type(std::move(val)) {}

    friend constexpr Group operator*(const Group &lhs, const Group &rhs) { return Group(op(lhs.value(), rhs.value())); }

    static constexpr auto get_inverse() { return inverse; }
    static constexpr Group one() { return Group(e()); }                    // return identity element.
    constexpr Group inv() const { return Group(inverse(this->value())); }  // return inverse element.
};

template <typename F, auto compose, auto id, typename X, auto mapping>
class OperatorMonoid : public Monoid<F, compose, id> {
    static_assert(std::is_invocable_r<X, decltype(mapping), F, X>::value);

public:
    using base_type = Monoid<F, compose, id>;
    using value_type = typename base_type::value_type;
    using acted_type = X;

    constexpr OperatorMonoid() : base_type() {}
    constexpr OperatorMonoid(const value_type &val) : base_type(val) {}
    constexpr OperatorMonoid(value_type &&val) : base_type(std::move(val)) {}

    friend constexpr OperatorMonoid operator*(const OperatorMonoid &lhs, const OperatorMonoid &rhs) { return OperatorMonoid(compose(lhs.value(), rhs.value())); }

    static constexpr auto get_mapping() { return mapping; }
    static constexpr OperatorMonoid one() { return OperatorMonoid(id()); }  // return identity mapping.
    constexpr acted_type act(const acted_type &x) const { return mapping(this->value(), x); }
    template <class S>
    constexpr S act(const S &x) const {
        static_assert(std::is_base_of<Set<acted_type>, S>::value);
        return S(mapping(this->value(), x.value()));
    }
};

namespace element {

template <typename S>
constexpr auto zero = []() -> S { return S(); };

template <typename S>
constexpr auto one = []() -> S { return 1; };

template <typename S>
constexpr auto min = []() -> S { return std::numeric_limits<S>::min(); };

template <typename S>
constexpr auto max = []() -> S { return std::numeric_limits<S>::max(); };

template <typename S>
constexpr auto one_below_max = []() -> S { return std::numeric_limits<S>::max() - 1; };

template <typename S>
constexpr auto lowest = []() -> S { return std::numeric_limits<S>::lowest(); };

template <typename S>
constexpr auto one_above_lowest = []() -> S { return std::numeric_limits<S>::lowest() + 1; };

}  // namespace element

namespace unary_operator {

template <typename S>
constexpr auto identity = [](const S &val) -> S { return val; };

template <typename S>
constexpr auto negate = [](const S &val) -> S { return -val; };

}  // namespace unary_operator

namespace binary_operator {

template <typename T, typename S = T>
constexpr auto plus = [](const T &lhs, const S &rhs) -> S { return lhs + rhs; };

template <typename T, typename S = T>
constexpr auto mul = [](const T &lhs, const S &rhs) -> S { return lhs * rhs; };

template <typename T, typename S = T>
constexpr auto bit_and = [](const T &lhs, const S &rhs) -> S { return lhs & rhs; };

template <typename T, typename S = T>
constexpr auto bit_or = [](const T &lhs, const S &rhs) -> S { return lhs | rhs; };

template <typename T, typename S = T>
constexpr auto bit_xor = [](const T &lhs, const S &rhs) -> S { return lhs ^ rhs; };

template <typename T, typename S = T>
constexpr auto min = [](const T &lhs, const S &rhs) -> S { return std::min<S>(lhs, rhs); };

template <typename T, typename S = T>
constexpr auto max = [](const T &lhs, const S &rhs) -> S { return std::max<S>(lhs, rhs); };

template <typename T, typename S = T>
constexpr auto gcd = [](const T &lhs, const S &rhs) -> S { return std::gcd(lhs, rhs); };

template <typename T, typename S = T>
constexpr auto lcm = [](const T &lhs, const S &rhs) -> S { return std::lcm(lhs, rhs); };

template <typename F, auto id, typename X = F>
constexpr auto assign_if_not_id = [](const F &lhs, const X &rhs) -> X {
    static_assert(std::is_invocable_r<F, decltype(id)>::value);
    return (lhs == id() ? rhs : lhs);
};

}  // namespace binary_operator

namespace monoid {

template <typename S>
using minimum = Monoid<S, binary_operator::min<S>, element::max<S>>;

template <typename S>
using minimum_safe = Monoid<S, binary_operator::min<S>, element::one_below_max<S>>;

template <typename S>
using maximum = Monoid<S, binary_operator::max<S>, element::lowest<S>>;

template <typename S>
using maximum_safe = Monoid<S, binary_operator::max<S>, element::one_above_lowest<S>>;

template <typename S>
using addition = Monoid<S, binary_operator::plus<S>, element::zero<S>>;

template <typename S>
using multiplication = Monoid<S, binary_operator::mul<S>, element::one<S>>;

template <typename S>
using bit_xor = Monoid<S, binary_operator::bit_xor<S>, element::zero<S>>;

}  // namespace monoid

namespace group {

template <typename S>
using addition = Group<S, binary_operator::plus<S>, element::zero<S>, unary_operator::negate<S>>;

template <typename S>
using bit_xor = Group<S, binary_operator::bit_xor<S>, element::zero<S>, unary_operator::identity<S>>;

}  // namespace group

namespace operator_monoid {

template <typename F, typename X = F>
using assign_for_minimum = OperatorMonoid<
    F, binary_operator::assign_if_not_id<F, element::max<F>>, element::max<F>,
    X, binary_operator::assign_if_not_id<F, element::max<F>, X>>;

template <typename F, typename X = F>
using assign_for_maximum = OperatorMonoid<
    F, binary_operator::assign_if_not_id<F, element::lowest<F>>, element::lowest<F>,
    X, binary_operator::assign_if_not_id<F, element::lowest<F>, X>>;

template <typename F, typename X = F>
using addition = OperatorMonoid<
    F, binary_operator::plus<F>, element::zero<F>,
    X, binary_operator::plus<F, X>>;

}  // namespace operator_monoid

}  // namespace algebra

}  // namespace algorithm


#line 11 "algorithm/DataStructure/SegmentTree/sparse_table.hpp"

namespace algorithm {

namespace sparse_table {

template <class IdempotentSemigroup>
class SparseTable {
public:
    using semigroup_type = IdempotentSemigroup;
    using value_type = semigroup_type::value_type;
    using size_type = std::size_t;

private:
    size_type m_sz;                                    // m_sz:=(要素数).
    std::vector<size_type> m_lg;                       // m_lg[x]:=floor(log2(x)).
    std::vector<std::vector<semigroup_type>> m_table;  // m_table[k][l]:=(区間[l,l+2^k)の総積).

public:
    // constructor. O(N log N).
    SparseTable() : m_sz(0), m_lg({0}), m_table({{}}) {}
    template <std::input_iterator InputIter>
    explicit SparseTable(InputIter first, InputIter last) : m_table(1, std::vector<semigroup_type>(first, last)) {
        m_sz = m_table[0].size();
        m_lg.assign(m_sz + 1, 0);
        for(size_type i = 2; i <= m_sz; ++i) m_lg[i] = m_lg[i >> 1] + 1;
        m_table.resize(m_lg[m_sz] + 1);
        for(size_type k = 1; k <= m_lg[m_sz]; ++k) {
            size_type n = m_sz - (1U << k) + 1;
            m_table[k].resize(n);
            for(size_type i = 0; i < n; ++i) m_table[k][i] = m_table[k - 1][i] * m_table[k - 1][i + (1U << (k - 1))];
        }
    }
    template <typename T>
    explicit SparseTable(std::initializer_list<T> il) : SparseTable(il.begin(), il.end()) {}

    // 要素数を取得する．
    size_type size() const { return m_sz; }
    // k番目の要素を取得する．O(1).
    value_type prod(size_type k) const {
        assert(k < size());
        return m_table[0][k].value();
    }
    // 区間[l,r)の要素の総積を求める．O(1).
    value_type prod(size_type l, size_type r) const {
        assert(l < r and r <= size());
        size_type k = m_lg[r - l];
        return (m_table[k][l] * m_table[k][r - (1U << k)]).value();
    }
    // 区間全体の要素の総積を求める．O(1).
    value_type prod_all() const {
        assert(size() > 0);
        return (m_table.back().front() * m_table.back().back()).value();
    }

    friend std::ostream &operator<<(std::ostream &os, const SparseTable &rhs) {
        os << "[\n";
        for(size_type k = 0; k <= rhs.m_lg.back(); ++k) {
            for(int i = 0, end = rhs.m_table[k].size(); i < end; ++i) os << (i == 0 ? "  [" : " ") << rhs.m_table[k][i];
            os << "]\n";
        }
        return os << "]";
    }
};

template <typename S>
using range_minimum_sparse_table = SparseTable<algebra::Semigroup<S, algebra::binary_operator::min<S>>>;

template <typename S>
using range_maximum_sparse_table = SparseTable<algebra::Semigroup<S, algebra::binary_operator::max<S>>>;

template <typename S>
using range_gcd_sparse_table = SparseTable<algebra::Semigroup<S, algebra::binary_operator::gcd<S>>>;

template <typename S>
using range_lcm_sparse_table = SparseTable<algebra::Semigroup<S, algebra::binary_operator::lcm<S>>>;

}  // namespace sparse_table

}  // namespace algorithm
Back to top page