sparse_table.hpp¶
数组不再修改且区间运算幂等（如最小值、最大值或 gcd）时，用 \(O(n\log n)\) 预处理把每次区间查询降到 \(O(1)\)。
Complexity: Time: O(n log n) build and O(1) idempotent range query. Space: O(n log n).
AC 记录：staticrmq。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @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 fn, auto e,
bool old = !std::is_same_v<decltype(fn), std::nullptr_t>>
struct sparse_table_algebra;
template <class Semilattice, auto fn, auto e>
struct sparse_table_algebra<Semilattice, fn, e, false> {
static_assert(std::is_same_v<decltype(e), 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 &l, const value_type &r) {
return Semilattice::op(l, r);
}
};
template <class Value, auto fn, auto e>
struct sparse_table_algebra<Value, fn, e, true> {
using value_type = Value;
static value_type unit() {
if constexpr (std::is_same_v<decltype(e), std::nullptr_t>) {
return value_type{};
} else {
return value_type(e);
}
}
static value_type op(const value_type &l, const value_type &r) {
return fn(l, r);
}
};
} // 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 fn = nullptr, auto e = nullptr>
class sparse_table {
using algebra_type = internal::sparse_table_algebra<Algebra, fn, e>;
public:
using value_type = typename algebra_type::value_type;
sparse_table() = default;
explicit sparse_table(const std::vector<value_type> &a) { build(a); }
/// @brief Rebuild from a static array.
void build(const std::vector<value_type> &a) {
n = int(a.size());
int lg = int(std::bit_width(static_cast<unsigned>(n)));
st.assign(lg, {});
if (n == 0) {
return;
}
st[0] = a;
for (int dep = 1; dep < lg; dep++) {
int w = 1 << dep;
int hf = w >> 1;
st[dep].resize(n - w + 1);
for (int l = 0; l + w <= n; l++) {
st[dep][l] = algebra_type::op(st[dep - 1][l], st[dep - 1][l + hf]);
}
}
}
int size() const { return n; }
bool empty() const { return n == 0; }
/// @brief Return the idempotent product over [l, r).
value_type prod(int l, int r) const {
assert(0 <= l && l <= r && r <= n);
if (l == r) {
return algebra_type::unit();
}
int dep = int(std::bit_width(static_cast<unsigned>(r - l))) - 1;
int w = 1 << dep;
return algebra_type::op(st[dep][l], st[dep][r - w]);
}
private:
int n = 0;
std::vector<std::vector<value_type>> st;
};
} // namespace noya
#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 fn, auto e,
bool old = !std::is_same_v<decltype(fn), std::nullptr_t>>
struct sparse_table_algebra;
template <class Semilattice, auto fn, auto e>
struct sparse_table_algebra<Semilattice, fn, e, false> {
static_assert(std::is_same_v<decltype(e), 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 &l, const value_type &r) {
return Semilattice::op(l, r);
}
};
template <class Value, auto fn, auto e>
struct sparse_table_algebra<Value, fn, e, true> {
using value_type = Value;
static value_type unit() {
if constexpr (std::is_same_v<decltype(e), std::nullptr_t>) {
return value_type{};
} else {
return value_type(e);
}
}
static value_type op(const value_type &l, const value_type &r) {
return fn(l, r);
}
};
} // 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 fn = nullptr, auto e = nullptr>
class sparse_table {
using algebra_type = internal::sparse_table_algebra<Algebra, fn, e>;
public:
using value_type = typename algebra_type::value_type;
sparse_table() = default;
explicit sparse_table(const std::vector<value_type> &a) { build(a); }
/// @brief Rebuild from a static array.
void build(const std::vector<value_type> &a) {
n = int(a.size());
int lg = int(std::bit_width(static_cast<unsigned>(n)));
st.assign(lg, {});
if (n == 0) {
return;
}
st[0] = a;
for (int dep = 1; dep < lg; dep++) {
int w = 1 << dep;
int hf = w >> 1;
st[dep].resize(n - w + 1);
for (int l = 0; l + w <= n; l++) {
st[dep][l] = algebra_type::op(st[dep - 1][l], st[dep - 1][l + hf]);
}
}
}
int size() const { return n; }
bool empty() const { return n == 0; }
/// @brief Return the idempotent product over [l, r).
value_type prod(int l, int r) const {
assert(0 <= l && l <= r && r <= n);
if (l == r) {
return algebra_type::unit();
}
int dep = int(std::bit_width(static_cast<unsigned>(r - l))) - 1;
int w = 1 << dep;
return algebra_type::op(st[dep][l], st[dep][r - w]);
}
private:
int n = 0;
std::vector<std::vector<value_type>> st;
};
} // 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 fn, auto e,
bool old = !std::is_same_v<decltype(fn), std::nullptr_t>>
struct sparse_table_algebra;
template <class Semilattice, auto fn, auto e>
struct sparse_table_algebra<Semilattice, fn, e, false> {
static_assert(std::is_same_v<decltype(e), 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 &l, const value_type &r) {
return Semilattice::op(l, r);
}
};
template <class Value, auto fn, auto e>
struct sparse_table_algebra<Value, fn, e, true> {
using value_type = Value;
static value_type unit() {
if constexpr (std::is_same_v<decltype(e), std::nullptr_t>) {
return value_type{};
} else {
return value_type(e);
}
}
static value_type op(const value_type &l, const value_type &r) {
return fn(l, r);
}
};
} // 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 fn = nullptr, auto e = nullptr>
class sparse_table {
using algebra_type = internal::sparse_table_algebra<Algebra, fn, e>;
public:
using value_type = typename algebra_type::value_type;
sparse_table() = default;
explicit sparse_table(const std::vector<value_type> &a) { build(a); }
/// @brief Rebuild from a static array.
void build(const std::vector<value_type> &a) {
n = int(a.size());
int lg = int(std::bit_width(static_cast<unsigned>(n)));
st.assign(lg, {});
if (n == 0) {
return;
}
st[0] = a;
for (int dep = 1; dep < lg; dep++) {
int w = 1 << dep;
int hf = w >> 1;
st[dep].resize(n - w + 1);
for (int l = 0; l + w <= n; l++) {
st[dep][l] = algebra_type::op(st[dep - 1][l], st[dep - 1][l + hf]);
}
}
}
int size() const { return n; }
bool empty() const { return n == 0; }
/// @brief Return the idempotent product over [l, r).
value_type prod(int l, int r) const {
assert(0 <= l && l <= r && r <= n);
if (l == r) {
return algebra_type::unit();
}
int dep = int(std::bit_width(static_cast<unsigned>(r - l))) - 1;
int w = 1 << dep;
return algebra_type::op(st[dep][l], st[dep][r - w]);
}
private:
int n = 0;
std::vector<std::vector<value_type>> st;
};
} // namespace noya