sparse_table.hpp¶
可重信息的静态区间查询：\(O(n\log n)\) 预处理、\(O(1)\) 查询。“可重”指同一段信息重复合并不改变答案，例如 min、max、gcd、按位与/或；求和和异或不适用。合并仍须满足结合律，数组不支持在线修改。
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 <utility>
#include <vector>
namespace noya {
/// @brief Static O(1) range product for an idempotent monoid.
/// Monoid provides value_type, unit(), and an associative, idempotent op().
/// Empty ranges return unit(); input arrays are owned by the table.
/// @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 Monoid> class sparse_table {
public:
using value_type = typename Monoid::value_type;
sparse_table() = default;
explicit sparse_table(std::vector<value_type> a) { build(std::move(a)); }
template <class F> sparse_table(int n_, F f) { build(n_, std::move(f)); }
template <class F> void build(int n_, F f) {
assert(n_ >= 0);
std::vector<value_type> a;
a.reserve(n_);
for (int i = 0; i < n_; i++) {
a.push_back(f(i));
}
build(std::move(a));
}
/// @brief Rebuild from a static array.
void build(std::vector<value_type> a) {
n = int(a.size());
int lg = int(std::bit_width(static_cast<unsigned>(n)));
st.resize(lg);
if (n == 0) {
return;
}
st[0] = std::move(a);
for (int dep = 1; dep < lg; dep++) {
int w = 1 << dep;
int hf = w >> 1;
int len = n - w + 1;
st[dep].resize(len, Monoid::unit());
for (int l = 0; l < len; l++) {
st[dep][l] = Monoid::op(st[dep - 1][l], st[dep - 1][l + hf]);
}
}
}
int size() const { return n; }
bool empty() const { return n == 0; }
value_type get(int p) const {
assert(0 <= p && p < n);
return st[0][p];
}
value_type all_prod() const { return prod(0, n); }
/// @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 Monoid::unit();
}
int dep = int(std::bit_width(static_cast<unsigned>(r - l))) - 1;
int w = 1 << dep;
return Monoid::op(st[dep][l], st[dep][r - w]);
}
private:
int n = 0;
std::vector<std::vector<value_type>> st;
};
} // namespace noya
// NOYA_SPARSE_TABLE_HPP
#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 <utility>
#include <vector>
namespace noya {
/// @brief Static O(1) range product for an idempotent monoid.
/// Monoid provides value_type, unit(), and an associative, idempotent op().
/// Empty ranges return unit(); input arrays are owned by the table.
/// @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 Monoid> class sparse_table {
public:
using value_type = typename Monoid::value_type;
sparse_table() = default;
explicit sparse_table(std::vector<value_type> a) { build(std::move(a)); }
template <class F> sparse_table(int n_, F f) { build(n_, std::move(f)); }
template <class F> void build(int n_, F f) {
assert(n_ >= 0);
std::vector<value_type> a;
a.reserve(n_);
for (int i = 0; i < n_; i++) {
a.push_back(f(i));
}
build(std::move(a));
}
/// @brief Rebuild from a static array.
void build(std::vector<value_type> a) {
n = int(a.size());
int lg = int(std::bit_width(static_cast<unsigned>(n)));
st.resize(lg);
if (n == 0) {
return;
}
st[0] = std::move(a);
for (int dep = 1; dep < lg; dep++) {
int w = 1 << dep;
int hf = w >> 1;
int len = n - w + 1;
st[dep].resize(len, Monoid::unit());
for (int l = 0; l < len; l++) {
st[dep][l] = Monoid::op(st[dep - 1][l], st[dep - 1][l + hf]);
}
}
}
int size() const { return n; }
bool empty() const { return n == 0; }
value_type get(int p) const {
assert(0 <= p && p < n);
return st[0][p];
}
value_type all_prod() const { return prod(0, n); }
/// @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 Monoid::unit();
}
int dep = int(std::bit_width(static_cast<unsigned>(r - l))) - 1;
int w = 1 << dep;
return Monoid::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
/// @complexity Time: O(n log n) build and O(1) idempotent range query.
/// Space: O(n log n).
#include <bit>
#include <cassert>
#include <utility>
#include <vector>
namespace noya {
/// @brief Static O(1) range product for an idempotent monoid.
/// Monoid provides value_type, unit(), and an associative, idempotent op().
/// Empty ranges return unit(); input arrays are owned by the table.
/// @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 Monoid> class sparse_table {
public:
using value_type = typename Monoid::value_type;
sparse_table() = default;
explicit sparse_table(std::vector<value_type> a) { build(std::move(a)); }
template <class F> sparse_table(int n_, F f) { build(n_, std::move(f)); }
template <class F> void build(int n_, F f) {
assert(n_ >= 0);
std::vector<value_type> a;
a.reserve(n_);
for (int i = 0; i < n_; i++) {
a.push_back(f(i));
}
build(std::move(a));
}
/// @brief Rebuild from a static array.
void build(std::vector<value_type> a) {
n = int(a.size());
int lg = int(std::bit_width(static_cast<unsigned>(n)));
st.resize(lg);
if (n == 0) {
return;
}
st[0] = std::move(a);
for (int dep = 1; dep < lg; dep++) {
int w = 1 << dep;
int hf = w >> 1;
int len = n - w + 1;
st[dep].resize(len, Monoid::unit());
for (int l = 0; l < len; l++) {
st[dep][l] = Monoid::op(st[dep - 1][l], st[dep - 1][l + hf]);
}
}
}
int size() const { return n; }
bool empty() const { return n == 0; }
value_type get(int p) const {
assert(0 <= p && p < n);
return st[0][p];
}
value_type all_prod() const { return prod(0, n); }
/// @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 Monoid::unit();
}
int dep = int(std::bit_width(static_cast<unsigned>(r - l))) - 1;
int w = 1 << dep;
return Monoid::op(st[dep][l], st[dep][r - w]);
}
private:
int n = 0;
std::vector<std::vector<value_type>> st;
};
} // namespace noya
// NOYA_SPARSE_TABLE_HPP