Disjoint Sparse Table
(Src/DataStructure/SparseTable/DisjointSparseTable.hpp)

• View this file on GitHub
• Last update: 2025-04-17 19:44:48+09:00
• Include: #include "Src/DataStructure/SparseTable/DisjointSparseTable.hpp"

struct M {
    using Element = ;
    static Element identity() {

    }
    static Element operation(Element L, Element R) {

    }
};

Depends on

• Src/Algebra/Monoid/MonoidConcept.hpp
• Src/Algebra/Semigroup/SemigroupConcept.hpp
• 標準データ型のエイリアス (Src/Template/TypeAlias.hpp)

Verified with

• Test/LC/staticrmq/DisjointSparseTable.test.cpp

Code

#pragma once

#include "../../Template/TypeAlias.hpp"
#include "../../Algebra/Monoid/MonoidConcept.hpp"

#include <bit>
#include <cassert>
#include <concepts>
#include <vector>

namespace zawa {

template <concepts::Monoid M>
class DisjointSparseTable {
public:

    using V = typename M::Element;

    constexpr usize height(usize n) const {
        return std::max(usize{1}, std::bit_width(n) - (usize)std::has_single_bit(n));
    }

    constexpr usize msb(usize n) const {
        assert(n);
        return std::bit_width(n) - 1;
    }

    DisjointSparseTable(std::vector<V>&& A) : m_table(height(A.size())) {
        assert(A.size());
        for (usize i = 1, w = 2 ; i < m_table.size() ; i++, w <<= 1) {
            m_table[i].resize(A.size());
            for (usize j = 0, idx = 0 ; j < A.size() ; j += w, idx++) {
                V prod = M::identity();
                if (idx & 1) { // ->
                    usize m = std::min(A.size() - j, w);
                    for (usize k = 0 ; k < m ; k++) {
                        prod = M::operation(prod, A[j + k]);
                        m_table[i][j + k] = prod;
                    }
                }
                else { // <-
                    usize m = std::min(A.size(), j + w);
                    for (usize k = m ; k-- > j ; ) {
                        prod = M::operation(A[k], prod);
                        m_table[i][k] = prod;
                    }
                }
            }
        }
        m_table[0] = std::move(A);
    }

    DisjointSparseTable(const std::vector<V>& A) : DisjointSparseTable(std::vector<V>{A}) {}

    template <std::input_iterator It>
    DisjointSparseTable(It first, It last) : DisjointSparseTable(std::vector(first, last)) {}

    V product(usize l, usize r) const {
        assert(l <= r and r <= m_table[0].size());
        if (l == r) return M::identity();
        if (l + 1 == r) return m_table[0][l];
        usize y = msb(l xor --r);
        return M::operation(m_table[y][l], m_table[y][r]);
    }

private:

    std::vector<std::vector<V>> m_table;
};

} // namespace zawa

#line 2 "Src/DataStructure/SparseTable/DisjointSparseTable.hpp"

#line 2 "Src/Template/TypeAlias.hpp"

#include <cstdint>
#include <cstddef>

namespace zawa {

using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;

using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;

using usize = std::size_t;

} // namespace zawa
#line 2 "Src/Algebra/Monoid/MonoidConcept.hpp"

#line 2 "Src/Algebra/Semigroup/SemigroupConcept.hpp"

#include <concepts>

namespace zawa {

namespace concepts {

template <class T>
concept Semigroup = requires {
    typename T::Element;
    { T::operation(std::declval<typename T::Element>(), std::declval<typename T::Element>()) } -> std::same_as<typename T::Element>;
};

} // namespace concepts

} // namespace zawa
#line 4 "Src/Algebra/Monoid/MonoidConcept.hpp"

#line 6 "Src/Algebra/Monoid/MonoidConcept.hpp"

namespace zawa {

namespace concepts {

template <class T>
concept Identitiable = requires {
    typename T::Element;
    { T::identity() } -> std::same_as<typename T::Element>;
};

template <class T>
concept Monoid = Semigroup<T> and Identitiable<T>;

} // namespace

} // namespace zawa
#line 5 "Src/DataStructure/SparseTable/DisjointSparseTable.hpp"

#include <bit>
#include <cassert>
#line 9 "Src/DataStructure/SparseTable/DisjointSparseTable.hpp"
#include <vector>

namespace zawa {

template <concepts::Monoid M>
class DisjointSparseTable {
public:

    using V = typename M::Element;

    constexpr usize height(usize n) const {
        return std::max(usize{1}, std::bit_width(n) - (usize)std::has_single_bit(n));
    }

    constexpr usize msb(usize n) const {
        assert(n);
        return std::bit_width(n) - 1;
    }

    DisjointSparseTable(std::vector<V>&& A) : m_table(height(A.size())) {
        assert(A.size());
        for (usize i = 1, w = 2 ; i < m_table.size() ; i++, w <<= 1) {
            m_table[i].resize(A.size());
            for (usize j = 0, idx = 0 ; j < A.size() ; j += w, idx++) {
                V prod = M::identity();
                if (idx & 1) { // ->
                    usize m = std::min(A.size() - j, w);
                    for (usize k = 0 ; k < m ; k++) {
                        prod = M::operation(prod, A[j + k]);
                        m_table[i][j + k] = prod;
                    }
                }
                else { // <-
                    usize m = std::min(A.size(), j + w);
                    for (usize k = m ; k-- > j ; ) {
                        prod = M::operation(A[k], prod);
                        m_table[i][k] = prod;
                    }
                }
            }
        }
        m_table[0] = std::move(A);
    }

    DisjointSparseTable(const std::vector<V>& A) : DisjointSparseTable(std::vector<V>{A}) {}

    template <std::input_iterator It>
    DisjointSparseTable(It first, It last) : DisjointSparseTable(std::vector(first, last)) {}

    V product(usize l, usize r) const {
        assert(l <= r and r <= m_table[0].size());
        if (l == r) return M::identity();
        if (l + 1 == r) return m_table[0][l];
        usize y = msb(l xor --r);
        return M::operation(m_table[y][l], m_table[y][r]);
    }

private:

    std::vector<std::vector<V>> m_table;
};

} // namespace zawa

Back to top page