sparse_table.hpp¶
Constant-time static range queries for associative, idempotent operations such as minimum, maximum, and gcd.
Verified by staticrmq.
数组不再修改且区间运算幂等（如最小值、最大值或 gcd）时，用 O(n log n) 预处理把每次区间查询降到 O(1)。
Implementation¶
#ifndef NOYA_SPARSE_TABLE_HPP
#define NOYA_SPARSE_TABLE_HPP 1
/// @complexity Time: O(n log n) build and O(1) idempotent range query.
/// Space: O(n log n).
#include <bit>
#include <cassert>
#include <cstddef>
#include <type_traits>
#include <vector>
namespace noya {
namespace internal {
template <class Algebra, auto Operation, auto Identity,
bool Legacy = !std::is_same_v<decltype(Operation), std::nullptr_t>>
struct sparse_table_algebra;
template <class Semilattice, auto Operation, auto Identity>
struct sparse_table_algebra<Semilattice, Operation, Identity, false> {
static_assert(std::is_same_v<decltype(Identity), std::nullptr_t>,
"a policy sparse_table gets its identity from unit()");
using value_type = typename Semilattice::value_type;
static value_type unit() { return Semilattice::unit(); }
static value_type op(const value_type &left, const value_type &right) {
return Semilattice::op(left, right);
}
};
template <class Value, auto Operation, auto Identity>
struct sparse_table_algebra<Value, Operation, Identity, true> {
using value_type = Value;
static value_type unit() {
if constexpr (std::is_same_v<decltype(Identity), std::nullptr_t>) {
return value_type{};
} else {
return value_type(Identity);
}
}
static value_type op(const value_type &left, const value_type &right) {
return Operation(left, right);
}
};
} // namespace internal
/// @brief Static O(1) range product for an idempotent semilattice.
/// The preferred interface is sparse_table<Semilattice>, where Semilattice
/// provides value_type, unit(), and an associative, idempotent op(). The legacy
/// sparse_table<Value, operation, identity> spelling remains supported.
/// @details For k = floor(log2(r-l)), [l, r) is covered by the length-2^k
/// blocks beginning at l and ending at r. They may overlap, so combining them
/// is correct precisely because op(x, x) = x.
template <class Algebra, auto Operation = nullptr, auto Identity = nullptr>
class sparse_table {
using algebra_type =
internal::sparse_table_algebra<Algebra, Operation, Identity>;
public:
using value_type = typename algebra_type::value_type;
sparse_table() = default;
explicit sparse_table(const std::vector<value_type> &values) {
build(values);
}
/// @brief Rebuild from a static array.
void build(const std::vector<value_type> &values) {
size_ = int(values.size());
int levels = int(std::bit_width(static_cast<unsigned>(size_)));
table_.assign(levels, {});
if (size_ == 0) {
return;
}
table_[0] = values;
for (int level = 1; level < levels; level++) {
int width = 1 << level;
int half = width >> 1;
table_[level].resize(size_ - width + 1);
for (int left = 0; left + width <= size_; left++) {
table_[level][left] = algebra_type::op(table_[level - 1][left],
table_[level - 1][left + half]);
}
}
}
int size() const { return size_; }
bool empty() const { return size_ == 0; }
/// @brief Return the idempotent product over [left, right).
value_type prod(int left, int right) const {
assert(0 <= left && left <= right && right <= size_);
if (left == right) {
return algebra_type::unit();
}
int level = int(std::bit_width(static_cast<unsigned>(right - left))) - 1;
int width = 1 << level;
return algebra_type::op(table_[level][left], table_[level][right - width]);
}
private:
int size_ = 0;
std::vector<std::vector<value_type>> table_;
};
} // namespace noya
#endif // NOYA_SPARSE_TABLE_HPP
#include <bit>
#include <cassert>
#include <cstddef>
#include <type_traits>
#include <vector>
/// @complexity Time: O(n log n) build and O(1) idempotent range query.
/// Space: O(n log n).
namespace noya {
namespace internal {
template <class Algebra, auto Operation, auto Identity,
bool Legacy = !std::is_same_v<decltype(Operation), std::nullptr_t>>
struct sparse_table_algebra;
template <class Semilattice, auto Operation, auto Identity>
struct sparse_table_algebra<Semilattice, Operation, Identity, false> {
static_assert(std::is_same_v<decltype(Identity), std::nullptr_t>,
"a policy sparse_table gets its identity from unit()");
using value_type = typename Semilattice::value_type;
static value_type unit() { return Semilattice::unit(); }
static value_type op(const value_type &left, const value_type &right) {
return Semilattice::op(left, right);
}
};
template <class Value, auto Operation, auto Identity>
struct sparse_table_algebra<Value, Operation, Identity, true> {
using value_type = Value;
static value_type unit() {
if constexpr (std::is_same_v<decltype(Identity), std::nullptr_t>) {
return value_type{};
} else {
return value_type(Identity);
}
}
static value_type op(const value_type &left, const value_type &right) {
return Operation(left, right);
}
};
} // namespace internal
/// @brief Static O(1) range product for an idempotent semilattice.
/// The preferred interface is sparse_table<Semilattice>, where Semilattice
/// provides value_type, unit(), and an associative, idempotent op(). The legacy
/// sparse_table<Value, operation, identity> spelling remains supported.
/// @details For k = floor(log2(r-l)), [l, r) is covered by the length-2^k
/// blocks beginning at l and ending at r. They may overlap, so combining them
/// is correct precisely because op(x, x) = x.
template <class Algebra, auto Operation = nullptr, auto Identity = nullptr>
class sparse_table {
using algebra_type =
internal::sparse_table_algebra<Algebra, Operation, Identity>;
public:
using value_type = typename algebra_type::value_type;
sparse_table() = default;
explicit sparse_table(const std::vector<value_type> &values) {
build(values);
}
/// @brief Rebuild from a static array.
void build(const std::vector<value_type> &values) {
size_ = int(values.size());
int levels = int(std::bit_width(static_cast<unsigned>(size_)));
table_.assign(levels, {});
if (size_ == 0) {
return;
}
table_[0] = values;
for (int level = 1; level < levels; level++) {
int width = 1 << level;
int half = width >> 1;
table_[level].resize(size_ - width + 1);
for (int left = 0; left + width <= size_; left++) {
table_[level][left] = algebra_type::op(table_[level - 1][left],
table_[level - 1][left + half]);
}
}
}
int size() const { return size_; }
bool empty() const { return size_ == 0; }
/// @brief Return the idempotent product over [left, right).
value_type prod(int left, int right) const {
assert(0 <= left && left <= right && right <= size_);
if (left == right) {
return algebra_type::unit();
}
int level = int(std::bit_width(static_cast<unsigned>(right - left))) - 1;
int width = 1 << level;
return algebra_type::op(table_[level][left], table_[level][right - width]);
}
private:
int size_ = 0;
std::vector<std::vector<value_type>> table_;
};
} // namespace noya