disjoint_sparse_table.hpp¶
预处理静态数组上任意可结合运算的区间乘积；不要求幂等，并以常数时间回答查询。
Complexity: Time: O(n log n) build and O(1) range product. Space: O(n log n).
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(n log n) build and O(1) range product.
/// Space: O(n log n).
#include <algorithm>
#include <cassert>
#include <utility>
#include <vector>
namespace noya {
/// @brief Static O(1) range product for an arbitrary associative monoid.
template <class Monoid> struct disjoint_sparse_table {
using value_type = typename Monoid::value_type;
int n = 0;
std::vector<value_type> a;
std::vector<std::vector<value_type>> st;
disjoint_sparse_table() = default;
explicit disjoint_sparse_table(std::vector<value_type> arr) {
build(std::move(arr));
}
template <class F> disjoint_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> arr;
arr.reserve(n_);
for (int i = 0; i < n_; i++) {
arr.push_back(f(i));
}
build(std::move(arr));
}
int size() const { return n; }
bool empty() const { return n == 0; }
value_type get(int p) const {
assert(0 <= p && p < n);
return a[p];
}
value_type all_prod() const { return prod(0, n); }
/// @brief Rebuild the table in O(n log n).
void build(std::vector<value_type> arr) {
a = std::move(arr);
n = int(a.size());
int lg = n <= 1 ? 0 : highest_bit(unsigned(n - 1)) + 1;
st.resize(lg);
for (int dep = 0; dep < lg; dep++) {
st[dep].resize(n, Monoid::unit());
int hf = 1 << dep;
int blk = hf << 1;
for (int st0 = 0; st0 < n; st0 += blk) {
int mid = std::min(st0 + hf, n);
int ed = std::min(st0 + blk, n);
if (st0 < mid) {
st[dep][mid - 1] = a[mid - 1];
for (int i = mid - 2; i >= st0; i--) {
st[dep][i] = Monoid::op(a[i], st[dep][i + 1]);
}
}
if (mid < ed) {
st[dep][mid] = a[mid];
for (int i = mid + 1; i < ed; i++) {
st[dep][i] = Monoid::op(st[dep][i - 1], a[i]);
}
}
}
}
}
/// @brief Return the monoid 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();
}
if (l + 1 == r) {
return a[l];
}
int dep = highest_bit(unsigned(l ^ (r - 1)));
return Monoid::op(st[dep][l], st[dep][r - 1]);
}
/// @brief Largest right such that predicate(prod(left, right)) is true.
template <class Predicate>
int max_right(int l, Predicate f) const {
assert(0 <= l && l <= n);
assert(f(Monoid::unit()));
int ok = l;
int bad = n + 1;
while (bad - ok > 1) {
int mid = ok + (bad - ok) / 2;
if (f(prod(l, mid))) {
ok = mid;
} else {
bad = mid;
}
}
return ok;
}
/// @brief Smallest left such that predicate(prod(left, right)) is true.
template <class Predicate>
int min_left(int r, Predicate f) const {
assert(0 <= r && r <= n);
assert(f(Monoid::unit()));
int ok = r;
int bad = -1;
while (ok - bad > 1) {
int mid = bad + (ok - bad) / 2;
if (f(prod(mid, r))) {
ok = mid;
} else {
bad = mid;
}
}
return ok;
}
private:
static int highest_bit(unsigned val) {
assert(val != 0);
return 31 - __builtin_clz(val);
}
};
} // namespace noya
// NOYA_DISJOINT_SPARSE_TABLE_HPP
#ifndef NOYA_DISJOINT_SPARSE_TABLE_HPP
#define NOYA_DISJOINT_SPARSE_TABLE_HPP 1
/// @complexity Time: O(n log n) build and O(1) range product.
/// Space: O(n log n).
#include <algorithm>
#include <cassert>
#include <utility>
#include <vector>
namespace noya {
/// @brief Static O(1) range product for an arbitrary associative monoid.
template <class Monoid> struct disjoint_sparse_table {
using value_type = typename Monoid::value_type;
int n = 0;
std::vector<value_type> a;
std::vector<std::vector<value_type>> st;
disjoint_sparse_table() = default;
explicit disjoint_sparse_table(std::vector<value_type> arr) {
build(std::move(arr));
}
template <class F> disjoint_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> arr;
arr.reserve(n_);
for (int i = 0; i < n_; i++) {
arr.push_back(f(i));
}
build(std::move(arr));
}
int size() const { return n; }
bool empty() const { return n == 0; }
value_type get(int p) const {
assert(0 <= p && p < n);
return a[p];
}
value_type all_prod() const { return prod(0, n); }
/// @brief Rebuild the table in O(n log n).
void build(std::vector<value_type> arr) {
a = std::move(arr);
n = int(a.size());
int lg = n <= 1 ? 0 : highest_bit(unsigned(n - 1)) + 1;
st.resize(lg);
for (int dep = 0; dep < lg; dep++) {
st[dep].resize(n, Monoid::unit());
int hf = 1 << dep;
int blk = hf << 1;
for (int st0 = 0; st0 < n; st0 += blk) {
int mid = std::min(st0 + hf, n);
int ed = std::min(st0 + blk, n);
if (st0 < mid) {
st[dep][mid - 1] = a[mid - 1];
for (int i = mid - 2; i >= st0; i--) {
st[dep][i] = Monoid::op(a[i], st[dep][i + 1]);
}
}
if (mid < ed) {
st[dep][mid] = a[mid];
for (int i = mid + 1; i < ed; i++) {
st[dep][i] = Monoid::op(st[dep][i - 1], a[i]);
}
}
}
}
}
/// @brief Return the monoid 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();
}
if (l + 1 == r) {
return a[l];
}
int dep = highest_bit(unsigned(l ^ (r - 1)));
return Monoid::op(st[dep][l], st[dep][r - 1]);
}
/// @brief Largest right such that predicate(prod(left, right)) is true.
template <class Predicate>
int max_right(int l, Predicate f) const {
assert(0 <= l && l <= n);
assert(f(Monoid::unit()));
int ok = l;
int bad = n + 1;
while (bad - ok > 1) {
int mid = ok + (bad - ok) / 2;
if (f(prod(l, mid))) {
ok = mid;
} else {
bad = mid;
}
}
return ok;
}
/// @brief Smallest left such that predicate(prod(left, right)) is true.
template <class Predicate>
int min_left(int r, Predicate f) const {
assert(0 <= r && r <= n);
assert(f(Monoid::unit()));
int ok = r;
int bad = -1;
while (ok - bad > 1) {
int mid = bad + (ok - bad) / 2;
if (f(prod(mid, r))) {
ok = mid;
} else {
bad = mid;
}
}
return ok;
}
private:
static int highest_bit(unsigned val) {
assert(val != 0);
return 31 - __builtin_clz(val);
}
};
} // namespace noya
#endif // NOYA_DISJOINT_SPARSE_TABLE_HPP
/// @complexity Time: O(n log n) build and O(1) range product.
/// Space: O(n log n).
#include <algorithm>
#include <cassert>
#include <utility>
#include <vector>
namespace noya {
/// @brief Static O(1) range product for an arbitrary associative monoid.
template <class Monoid> struct disjoint_sparse_table {
using value_type = typename Monoid::value_type;
int n = 0;
std::vector<value_type> a;
std::vector<std::vector<value_type>> st;
disjoint_sparse_table() = default;
explicit disjoint_sparse_table(std::vector<value_type> arr) {
build(std::move(arr));
}
template <class F> disjoint_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> arr;
arr.reserve(n_);
for (int i = 0; i < n_; i++) {
arr.push_back(f(i));
}
build(std::move(arr));
}
int size() const { return n; }
bool empty() const { return n == 0; }
value_type get(int p) const {
assert(0 <= p && p < n);
return a[p];
}
value_type all_prod() const { return prod(0, n); }
/// @brief Rebuild the table in O(n log n).
void build(std::vector<value_type> arr) {
a = std::move(arr);
n = int(a.size());
int lg = n <= 1 ? 0 : highest_bit(unsigned(n - 1)) + 1;
st.resize(lg);
for (int dep = 0; dep < lg; dep++) {
st[dep].resize(n, Monoid::unit());
int hf = 1 << dep;
int blk = hf << 1;
for (int st0 = 0; st0 < n; st0 += blk) {
int mid = std::min(st0 + hf, n);
int ed = std::min(st0 + blk, n);
if (st0 < mid) {
st[dep][mid - 1] = a[mid - 1];
for (int i = mid - 2; i >= st0; i--) {
st[dep][i] = Monoid::op(a[i], st[dep][i + 1]);
}
}
if (mid < ed) {
st[dep][mid] = a[mid];
for (int i = mid + 1; i < ed; i++) {
st[dep][i] = Monoid::op(st[dep][i - 1], a[i]);
}
}
}
}
}
/// @brief Return the monoid 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();
}
if (l + 1 == r) {
return a[l];
}
int dep = highest_bit(unsigned(l ^ (r - 1)));
return Monoid::op(st[dep][l], st[dep][r - 1]);
}
/// @brief Largest right such that predicate(prod(left, right)) is true.
template <class Predicate>
int max_right(int l, Predicate f) const {
assert(0 <= l && l <= n);
assert(f(Monoid::unit()));
int ok = l;
int bad = n + 1;
while (bad - ok > 1) {
int mid = ok + (bad - ok) / 2;
if (f(prod(l, mid))) {
ok = mid;
} else {
bad = mid;
}
}
return ok;
}
/// @brief Smallest left such that predicate(prod(left, right)) is true.
template <class Predicate>
int min_left(int r, Predicate f) const {
assert(0 <= r && r <= n);
assert(f(Monoid::unit()));
int ok = r;
int bad = -1;
while (ok - bad > 1) {
int mid = bad + (ok - bad) / 2;
if (f(prod(mid, r))) {
ok = mid;
} else {
bad = mid;
}
}
return ok;
}
private:
static int highest_bit(unsigned val) {
assert(val != 0);
return 31 - __builtin_clz(val);
}
};
} // namespace noya
// NOYA_DISJOINT_SPARSE_TABLE_HPP