disjoint_sparse_table.hpp¶
Static O(1) range product for an arbitrary associative monoid.
预处理静态数组上任意可结合运算的区间乘积；不要求幂等，并以常数时间回答查询。
Implementation¶
#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 <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> values;
std::vector<std::vector<value_type>> table;
disjoint_sparse_table() = default;
explicit disjoint_sparse_table(const std::vector<value_type> &input) {
build(input);
}
/// @brief Rebuild the table in O(n log n).
void build(const std::vector<value_type> &input) {
values = input;
n = int(values.size());
int levels = n <= 1 ? 0 : highest_bit(unsigned(n - 1)) + 1;
table.assign(levels, std::vector<value_type>(n, Monoid::unit()));
for (int level = 0; level < levels; level++) {
int half = 1 << level;
int block = half << 1;
for (int start = 0; start < n; start += block) {
int middle = std::min(start + half, n);
int finish = std::min(start + block, n);
if (start < middle) {
table[level][middle - 1] = values[middle - 1];
for (int i = middle - 2; i >= start; i--) {
table[level][i] = Monoid::op(values[i], table[level][i + 1]);
}
}
if (middle < finish) {
table[level][middle] = values[middle];
for (int i = middle + 1; i < finish; i++) {
table[level][i] = Monoid::op(table[level][i - 1], values[i]);
}
}
}
}
}
/// @brief Return the monoid product over [left, right).
value_type prod(int left, int right) const {
assert(0 <= left && left <= right && right <= n);
if (left == right) {
return Monoid::unit();
}
if (left + 1 == right) {
return values[left];
}
int level = highest_bit(unsigned(left ^ (right - 1)));
return Monoid::op(table[level][left], table[level][right - 1]);
}
/// @brief Largest right such that predicate(prod(left, right)) is true.
template <class Predicate>
int max_right(int left, Predicate predicate) const {
assert(0 <= left && left <= n);
assert(predicate(Monoid::unit()));
int good = left;
int bad = n + 1;
while (bad - good > 1) {
int middle = good + (bad - good) / 2;
if (predicate(prod(left, middle))) {
good = middle;
} else {
bad = middle;
}
}
return good;
}
/// @brief Smallest left such that predicate(prod(left, right)) is true.
template <class Predicate>
int min_left(int right, Predicate predicate) const {
assert(0 <= right && right <= n);
assert(predicate(Monoid::unit()));
int good = right;
int bad = -1;
while (good - bad > 1) {
int middle = bad + (good - bad) / 2;
if (predicate(prod(middle, right))) {
good = middle;
} else {
bad = middle;
}
}
return good;
}
private:
static int highest_bit(unsigned value) {
assert(value != 0);
return 31 - __builtin_clz(value);
}
};
} // namespace noya
#endif // NOYA_DISJOINT_SPARSE_TABLE_HPP
#include <algorithm>
#include <cassert>
#include <vector>
/// @complexity Time: O(n log n) build and O(1) range product.
/// Space: O(n log n).
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> values;
std::vector<std::vector<value_type>> table;
disjoint_sparse_table() = default;
explicit disjoint_sparse_table(const std::vector<value_type> &input) {
build(input);
}
/// @brief Rebuild the table in O(n log n).
void build(const std::vector<value_type> &input) {
values = input;
n = int(values.size());
int levels = n <= 1 ? 0 : highest_bit(unsigned(n - 1)) + 1;
table.assign(levels, std::vector<value_type>(n, Monoid::unit()));
for (int level = 0; level < levels; level++) {
int half = 1 << level;
int block = half << 1;
for (int start = 0; start < n; start += block) {
int middle = std::min(start + half, n);
int finish = std::min(start + block, n);
if (start < middle) {
table[level][middle - 1] = values[middle - 1];
for (int i = middle - 2; i >= start; i--) {
table[level][i] = Monoid::op(values[i], table[level][i + 1]);
}
}
if (middle < finish) {
table[level][middle] = values[middle];
for (int i = middle + 1; i < finish; i++) {
table[level][i] = Monoid::op(table[level][i - 1], values[i]);
}
}
}
}
}
/// @brief Return the monoid product over [left, right).
value_type prod(int left, int right) const {
assert(0 <= left && left <= right && right <= n);
if (left == right) {
return Monoid::unit();
}
if (left + 1 == right) {
return values[left];
}
int level = highest_bit(unsigned(left ^ (right - 1)));
return Monoid::op(table[level][left], table[level][right - 1]);
}
/// @brief Largest right such that predicate(prod(left, right)) is true.
template <class Predicate>
int max_right(int left, Predicate predicate) const {
assert(0 <= left && left <= n);
assert(predicate(Monoid::unit()));
int good = left;
int bad = n + 1;
while (bad - good > 1) {
int middle = good + (bad - good) / 2;
if (predicate(prod(left, middle))) {
good = middle;
} else {
bad = middle;
}
}
return good;
}
/// @brief Smallest left such that predicate(prod(left, right)) is true.
template <class Predicate>
int min_left(int right, Predicate predicate) const {
assert(0 <= right && right <= n);
assert(predicate(Monoid::unit()));
int good = right;
int bad = -1;
while (good - bad > 1) {
int middle = bad + (good - bad) / 2;
if (predicate(prod(middle, right))) {
good = middle;
} else {
bad = middle;
}
}
return good;
}
private:
static int highest_bit(unsigned value) {
assert(value != 0);
return 31 - __builtin_clz(value);
}
};
} // namespace noya